Re: [PATCH 5/6] x86: kaslr: select memory region from e820 maps

Re: [PATCH 5/6] x86: kaslr: select memory region from e820 maps

[George Spelvin]

As a logic simplification, the following gets rid of one variable
that's simply not needed.  (And adds a "static" declaration that seems
to be appropriate):

static bool largest_ram_region(unsigned long *start, unsigned long *size)
{
	int i;

	*size = 0;
	for (i = 0; i < real_mode->e820_entries; i++) {
		struct e820entry *entry = &real_mode->e820_map[i];

		if (entry->type != E820_RAM)
			continue;

		if (entry->size > *size) {
			*size = entry->size;
			*start = entry->addr;
		}
	}
	return *size != 0;
}

but I might instead do it as:

struct e820_entry const *largest_ram_region()
{
	struct e820_entry const *rc = NULL;
	unsigned long size = 0;
	int i;

	for (i = 0; i < real_mode->e820_entries; i++) {
		struct e820entry const *entry = &real_mode->e820_map[i];

		if (entry->type == E820_RAM && entry->size > size) {
			size = entry->size;
			rc = entry;
		}
	}
	return rc;
}

... with appropriate adjustments to the caller.  Anyway,
your choice.

Re: [PATCH 5/6] x86: kaslr: select memory region from e820 maps

[Kees Cook]

On Fri, Apr 26, 2013 at 2:51 PM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Fri, Apr 26, 2013 at 12:03 PM, Kees Cook <keescook@chromium.org> wrote:
>> This chooses the largest contiguous RAM region for the KASLR offset
>> to live in.
>>
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>> v2:
>>  - make sure to exclude e820 regions outside the 32-bit memory range.
>
> Do you need to execlude range that is used for initrd and possible
> command_line and boot_param ?

Yeah, and while doing a stress test here, I realized there's another
problem. In the original version of this, the stack and heap are set
up after relocation. In the C port, they're set up before, so there's
even more to avoid. To illustrate... here's a CONFIG_RELOCATABLE=n
boot:

LOAD_PHYS:0x0000000001000000
input:    0x0000000001dfe24d-0x00000000023db865
output:   0x0000000001000000-0x00000000023c98c0
heap:     0x00000000023e0740-0x00000000023e8740
stack:    0x00000000023ec698
chosen:   0x0000000001000000

(stack is just cheating and reporting sp in decompress_kernel)

And a CONFIG_RELOCATABLE=y and "noaslr" boot:

LOAD_PHYS:0x0000000001000000
input:    0x000000000108b25e-0x00000000016b3e96
output:   0x0000000000200000-0x00000000016a1db8
heap:     0x00000000016b9600-0x00000000016c1600
stack:    0x00000000016c5558
chosen:   0x0000000000200000

In that case, it's just so far under LOAD_PHYSICAL_START that it's
safe. But if KASLR picks an area overlapping input, heap, or stack
it's hosed. :)

-Kees

--
Kees Cook
Chrome OS Security

Re: [PATCH 5/6] x86: kaslr: select memory region from e820 maps

[H. Peter Anvin]

On 04/26/2013 02:51 PM, Yinghai Lu wrote:
> On Fri, Apr 26, 2013 at 12:03 PM, Kees Cook <keescook@chromium.org> wrote:
>> This chooses the largest contiguous RAM region for the KASLR offset
>> to live in.
>>
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>> v2:
>>  - make sure to exclude e820 regions outside the 32-bit memory range.
> 
> Do you need to execlude range that is used for initrd and possible
> command_line and boot_param ?
> 

Yes, those would have to be excluded.  For correctness the mem= and
memmap= options should also be taken into account.

	-hpa

Re: [PATCH 5/6] x86: kaslr: select memory region from e820 maps

[Yinghai Lu]

On Fri, Apr 26, 2013 at 12:03 PM, Kees Cook <keescook@chromium.org> wrote:
> This chooses the largest contiguous RAM region for the KASLR offset
> to live in.
>
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
> v2:
>  - make sure to exclude e820 regions outside the 32-bit memory range.

Do you need to execlude range that is used for initrd and possible
command_line and boot_param ?

Yinghai

[PATCH 5/6] x86: kaslr: select memory region from e820 maps

[Kees Cook]

This chooses the largest contiguous RAM region for the KASLR offset
to live in.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
v2:
 - make sure to exclude e820 regions outside the 32-bit memory range.
---
 arch/x86/boot/compressed/aslr.c |   47 ++++++++++++++++++++++++++++++++++-----
 1 file changed, 41 insertions(+), 6 deletions(-)

diff --git a/arch/x86/boot/compressed/aslr.c b/arch/x86/boot/compressed/aslr.c
index 4647e3f..3d3789e 100644
--- a/arch/x86/boot/compressed/aslr.c
+++ b/arch/x86/boot/compressed/aslr.c
@@ -2,6 +2,7 @@
 
 #ifdef CONFIG_RANDOMIZE_BASE
 #include <asm/msr.h>
+#include <asm/e820.h>
 
 #include <asm/archrandom.h>
 static inline int rdrand(unsigned long *v)
@@ -48,28 +49,62 @@ static unsigned long get_random_long(void)
 	return 0;
 }
 
+int largest_ram_region(unsigned long *start, unsigned long *size)
+{
+	int i, rc = 0;
+
+	*size = 0;
+	for (i = 0; i < real_mode->e820_entries; i++) {
+		struct e820entry *entry = &real_mode->e820_map[i];
+
+		if (entry->type != E820_RAM)
+			continue;
+
+		/* XXX: Handle arbitrary physical location. */
+		if (entry->addr > UINT_MAX)
+			continue;
+
+		if (entry->size > *size) {
+			*size = entry->size;
+			*start = entry->addr;
+			rc = 1;
+		}
+	}
+	return rc;
+}
+
 unsigned char *choose_kernel_location(unsigned char *hint, unsigned long size)
 {
 	unsigned char *choice = hint;
 	unsigned long random, mask;
+	unsigned long addr, length;
 
 	if (cmdline_find_option_bool("noaslr")) {
 		debug_putstr("KASLR disabled...\n");
 		goto out;
 	}
 
+	/* Find an appropriate E820 entry. */
+	if (!largest_ram_region(&addr, &length)) {
+		debug_putstr("KASLR could not find suitable E820 region...\n");
+		goto out;
+	}
+
 	random = get_random_long();
 
-	/* Clip off top of the range. */
+	/* XXX: Rework page tables to handle arbitrary physical location. */
 	mask = CONFIG_RANDOMIZE_BASE_MAX_OFFSET - 1;
 	random &= mask;
 
-	/* XXX: Find an appropriate E820 hole, instead of adding hint. */
-	random += (unsigned long)hint;
+	/* Clip to E820 entry size. */
+	while (random > length)
+		random >>= 1;
+
+	/* Offset the target. */
+	random += addr;
 
-	/* XXX: Clip to E820 hole, instead of just using hint. */
-	mask = (unsigned long)hint + CONFIG_RANDOMIZE_BASE_MAX_OFFSET;
-	while (random + size > mask)
+	/* Clip end to E820 entry size. */
+	while (random + size > addr + length)
 		random >>= 1;
 
 	/* Clip off bottom of range (via alignment). */
-- 
1.7.9.5

[PATCH 5/6] x86: kaslr: select memory region from e820 maps

[Kees Cook]

This chooses the largest contiguous RAM region for the KASLR offset
to live in.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/aslr.c |   43 +++++++++++++++++++++++++++++++++------
 1 file changed, 37 insertions(+), 6 deletions(-)

diff --git a/arch/x86/boot/compressed/aslr.c b/arch/x86/boot/compressed/aslr.c
index 11a91c6..8f21ebe 100644
--- a/arch/x86/boot/compressed/aslr.c
+++ b/arch/x86/boot/compressed/aslr.c
@@ -1,6 +1,7 @@
 #include "misc.h"
 
 #ifdef CONFIG_RANDOMIZE_BASE
+#include <asm/e820.h>
 
 #include <asm/archrandom.h>
 static inline int rdrand(unsigned long *v)
@@ -56,28 +57,58 @@ static unsigned long get_random_long(void)
 	return 0;
 }
 
+int largest_ram_region(unsigned long *start, unsigned long *size)
+{
+	int i, rc = 0;
+
+	*size = 0;
+	for (i = 0; i < real_mode->e820_entries; i++) {
+		struct e820entry *entry = &real_mode->e820_map[i];
+
+		if (entry->type != E820_RAM)
+			continue;
+
+		if (entry->size > *size) {
+			*size = entry->size;
+			*start = entry->addr;
+			rc = 1;
+		}
+	}
+	return rc;
+}
+
 unsigned char *choose_kernel_location(unsigned char *hint, unsigned long size)
 {
 	unsigned char *choice = hint;
 	unsigned long random, mask;
+	unsigned long addr, length;
 
 	if (cmdline_find_option_bool("noaslr")) {
 		debug_putstr("KASLR disabled...\n");
 		goto out;
 	}
 
+	/* Find an appropriate E820 entry. */
+	if (!largest_ram_region(&addr, &length)) {
+		debug_putstr("KASLR could not find suitable E820 region...\n");
+		goto out;
+	}
+
 	random = get_random_long();
 
-	/* Clip off top of the range. */
+	/* XXX: Rework page tables to handle arbitrary physical location. */
 	mask = CONFIG_RANDOMIZE_BASE_MAX_OFFSET - 1;
 	random &= mask;
 
-	/* XXX: Find an appropriate E820 hole, instead of adding hint. */
-	random += (unsigned long)hint;
+	/* Clip to E820 entry size. */
+	while (random > length)
+		random >>= 1;
+
+	/* Offset the target. */
+	random += addr;
 
-	/* XXX: Clip to E820 hole, instead of just using hint. */
-	mask = (unsigned long)hint + CONFIG_RANDOMIZE_BASE_MAX_OFFSET;
-	while (random + size > mask)
+	/* Clip end to E820 entry size. */
+	while (random + size > addr + length)
 		random >>= 1;
 
 	/* Clip off bottom of range (via alignment). */
-- 
1.7.9.5