[PATCH 0/5] x86, boot: clean up KASLR code (step 2)

[PATCH 0/5] x86, boot: clean up KASLR code (step 2)

[Kees Cook]

This is the next step in various clean-ups and small improvements of the
KASLR code. We're now moving past refactorings and have started making
small changes to code along with some related clean-ups.

After this series, the more major changes are coming. If there are other
things that are worth cleaning up before then, we should identify them
now. (Some cleanups have not been done now are because they're tied
to the major changes, like renaming "run_size" to "kernel_total_size"
since doing that rename in the existing code makes things uglier, IMO.)

-Kees

[PATCH 1/5] x86, KASLR: Update description for decompressor worst case size

[Kees Cook]

From: Baoquan He <bhe@redhat.com>

The comment that describes the analysis for the size of the decompressor
code only took gzip into account (there are currently 6 other decompressors
that could be used). The actual z_extract_offset calculation in code was
already handling the correct maximum size, but this documentation hadn't
been updated. This updates the documentation, fixes several typos, moves
the comment to header.S, updates references, and adds a note at the end
of the decompressor include list to remind us about updating the comment
in the future.

(Instead of moving the comment to mkpiggy.c, where the calculation
is currently happening, it is being moved to header.S because
the calculations in mkpiggy.c will be removed in favor of header.S
calculations in a following patch, and it seemed like overkill to move
the giant comment twice, especially when there's already reference to
z_extract_offset in header.S.)

Signed-off-by: Baoquan He <bhe@redhat.com>
[kees: rewrote changelog, cleaned up comment style, moved comments around]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c |  2 +-
 arch/x86/boot/compressed/misc.c  | 89 ++++------------------------------------
 arch/x86/boot/header.S           | 87 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 96 insertions(+), 82 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 9c29e7885ef0..7d86c5dd8e99 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -155,7 +155,7 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 
 	/*
 	 * Avoid the region that is unsafe to overlap during
-	 * decompression (see calculations at top of misc.c).
+	 * decompression (see calculations in ../header.S).
 	 */
 	unsafe_len = (output_size >> 12) + 32768 + 18;
 	unsafe = (unsigned long)input + input_size - unsafe_len;
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index ad8c01ac2885..e96829bdb6d2 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -14,90 +14,13 @@
 #include "misc.h"
 #include "../string.h"
 
-/* WARNING!!
- * This code is compiled with -fPIC and it is relocated dynamically
- * at run time, but no relocation processing is performed.
- * This means that it is not safe to place pointers in static structures.
- */
-
 /*
- * Getting to provable safe in place decompression is hard.
- * Worst case behaviours need to be analyzed.
- * Background information:
- *
- * The file layout is:
- *    magic[2]
- *    method[1]
- *    flags[1]
- *    timestamp[4]
- *    extraflags[1]
- *    os[1]
- *    compressed data blocks[N]
- *    crc[4] orig_len[4]
- *
- * resulting in 18 bytes of non compressed data overhead.
- *
- * Files divided into blocks
- * 1 bit (last block flag)
- * 2 bits (block type)
- *
- * 1 block occurs every 32K -1 bytes or when there 50% compression
- * has been achieved. The smallest block type encoding is always used.
- *
- * stored:
- *    32 bits length in bytes.
- *
- * fixed:
- *    magic fixed tree.
- *    symbols.
- *
- * dynamic:
- *    dynamic tree encoding.
- *    symbols.
- *
- *
- * The buffer for decompression in place is the length of the
- * uncompressed data, plus a small amount extra to keep the algorithm safe.
- * The compressed data is placed at the end of the buffer.  The output
- * pointer is placed at the start of the buffer and the input pointer
- * is placed where the compressed data starts.  Problems will occur
- * when the output pointer overruns the input pointer.
- *
- * The output pointer can only overrun the input pointer if the input
- * pointer is moving faster than the output pointer.  A condition only
- * triggered by data whose compressed form is larger than the uncompressed
- * form.
- *
- * The worst case at the block level is a growth of the compressed data
- * of 5 bytes per 32767 bytes.
- *
- * The worst case internal to a compressed block is very hard to figure.
- * The worst case can at least be boundined by having one bit that represents
- * 32764 bytes and then all of the rest of the bytes representing the very
- * very last byte.
- *
- * All of which is enough to compute an amount of extra data that is required
- * to be safe.  To avoid problems at the block level allocating 5 extra bytes
- * per 32767 bytes of data is sufficient.  To avoind problems internal to a
- * block adding an extra 32767 bytes (the worst case uncompressed block size)
- * is sufficient, to ensure that in the worst case the decompressed data for
- * block will stop the byte before the compressed data for a block begins.
- * To avoid problems with the compressed data's meta information an extra 18
- * bytes are needed.  Leading to the formula:
- *
- * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
- *
- * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
- * Adding 32768 instead of 32767 just makes for round numbers.
- * Adding the decompressor_size is necessary as it musht live after all
- * of the data as well.  Last I measured the decompressor is about 14K.
- * 10K of actual data and 4K of bss.
- *
+ * WARNING!!
+ * This code is compiled with -fPIC and it is relocated dynamically at
+ * run time, but no relocation processing is performed. This means that
+ * it is not safe to place pointers in static structures.
  */
 
-/*
- * gzip declarations
- */
 #define STATIC		static
 
 #undef memcpy
@@ -148,6 +71,10 @@ static int lines, cols;
 #ifdef CONFIG_KERNEL_LZ4
 #include "../../../../lib/decompress_unlz4.c"
 #endif
+/*
+ * NOTE: When adding a new decompressor, please update the analysis in
+ * ../header.S.
+ */
 
 static void scroll(void)
 {
diff --git a/arch/x86/boot/header.S b/arch/x86/boot/header.S
index 6236b9ec4b76..6b8f8728c1fa 100644
--- a/arch/x86/boot/header.S
+++ b/arch/x86/boot/header.S
@@ -440,6 +440,93 @@ setup_data:		.quad 0			# 64-bit physical pointer to
 
 pref_address:		.quad LOAD_PHYSICAL_ADDR	# preferred load addr
 
+#
+# Getting to provably safe in-place decompression is hard. Worst case
+# behaviours need be analyzed. Here let's take decompressing gzip-compressed
+# kernel as example to illustrate it:
+#
+# The file layout of gzip compressed kernel is as follows. For more
+# information, please refer to RFC 1951 and RFC 1952.
+#
+#    magic[2]
+#    method[1]
+#    flags[1]
+#    timestamp[4]
+#    extraflags[1]
+#    os[1]
+#    compressed data blocks[N]
+#    crc[4] orig_len[4]
+#
+# resulting in 18 bytes of non compressed data overhead.
+#
+# Files divided into blocks
+# 1 bit (last block flag)
+# 2 bits (block type)
+#
+# 1 block occurs every 32K -1 bytes or when there 50% compression
+# has been achieved. The smallest block type encoding is always used.
+#
+# stored:
+#    32 bits length in bytes.
+#
+# fixed:
+#    magic fixed tree.
+#    symbols.
+#
+# dynamic:
+#    dynamic tree encoding.
+#    symbols.
+#
+#
+# The buffer for decompression in place is the length of the uncompressed
+# data, plus a small amount extra to keep the algorithm safe. The
+# compressed data is placed at the end of the buffer.  The output pointer
+# is placed at the start of the buffer and the input pointer is placed
+# where the compressed data starts. Problems will occur when the output
+# pointer overruns the input pointer.
+#
+# The output pointer can only overrun the input pointer if the input
+# pointer is moving faster than the output pointer.  A condition only
+# triggered by data whose compressed form is larger than the uncompressed
+# form.
+#
+# The worst case at the block level is a growth of the compressed data
+# of 5 bytes per 32767 bytes.
+#
+# The worst case internal to a compressed block is very hard to figure.
+# The worst case can at least be bounded by having one bit that represents
+# 32764 bytes and then all of the rest of the bytes representing the very
+# very last byte.
+#
+# All of which is enough to compute an amount of extra data that is required
+# to be safe.  To avoid problems at the block level allocating 5 extra bytes
+# per 32767 bytes of data is sufficient.  To avoid problems internal to a
+# block adding an extra 32767 bytes (the worst case uncompressed block size)
+# is sufficient, to ensure that in the worst case the decompressed data for
+# block will stop the byte before the compressed data for a block begins.
+# To avoid problems with the compressed data's meta information an extra 18
+# bytes are needed.  Leading to the formula:
+#
+# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
+#
+# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
+# Adding 32768 instead of 32767 just makes for round numbers.
+# Adding the decompressor_size is necessary as it musht live after all
+# of the data as well.  Last I measured the decompressor is about 14K.
+# 10K of actual data and 4K of bss.
+#
+# Above analysis is for decompressing gzip compressed kernel only. Up to
+# now 6 different decompressor are supported all together. And among them
+# xz stores data in chunks and has maximum chunk of 64K. Hence safety
+# margin should be updated to cover all decompressors so that we don't
+# need to deal with each of them separately. Please check
+# the description in lib/decompressor_xxx.c for specific information.
+#
+# extra_bytes = (uncompressed_size >> 12) + 65536 + 128
+#
+# Note that this calculation, which results in z_extract_offset (below),
+# is currently generated in compressed/mkpiggy.c
+
 #define ZO_INIT_SIZE	(ZO__end - ZO_startup_32 + ZO_z_extract_offset)
 #define VO_INIT_SIZE	(VO__end - VO__text)
 #if ZO_INIT_SIZE > VO_INIT_SIZE
-- 
2.6.3

[PATCH 2/5] x86, KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[Kees Cook]

From: Baoquan He <bhe@redhat.com>

Currently CONFIG_RANDOMIZE_BASE_MAX_OFFSET is used to limit the maximum
offset for kernel randomization. This limit doesn't need to be a CONFIG
since it is tied completely to KERNEL_IMAGE_SIZE, and will make no sense
once physical and virtual offsets are randomized separately. This patch
removes CONFIG_RANDOMIZE_BASE_MAX_OFFSET and consolidates the Kconfig
help text.

Signed-off-by: Baoquan He <bhe@redhat.com>
[kees: rewrote changelog, dropped KERNEL_IMAGE_SIZE_DEFAULT, rewrote help]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/Kconfig                     | 72 ++++++++++++++----------------------
 arch/x86/boot/compressed/kaslr.c     | 12 +++---
 arch/x86/include/asm/page_64_types.h |  8 ++--
 arch/x86/mm/init_32.c                |  3 --
 4 files changed, 36 insertions(+), 59 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 2dc18605831f..5892d549596d 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -1932,54 +1932,38 @@ config RELOCATABLE
 	  (CONFIG_PHYSICAL_START) is used as the minimum location.
 
 config RANDOMIZE_BASE
-	bool "Randomize the address of the kernel image"
+	bool "Randomize the address of the kernel image (KASLR)"
 	depends on RELOCATABLE
 	default n
 	---help---
-	   Randomizes the physical and virtual address at which the
-	   kernel image is decompressed, as a security feature that
-	   deters exploit attempts relying on knowledge of the location
-	   of kernel internals.
+	  In support of Kernel Address Space Layout Randomization (KASLR),
+	  this randomizes the physical address at which the kernel image
+	  is decompressed and the virtual address where the kernel
+	  image is mapped, as a security feature that deters exploit
+	  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.)
+
+	  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.
+
+	  If CONFIG_HIBERNATE is also enabled, KASLR is disabled at boot
+	  time. To enable it, boot with "kaslr" on the kernel command
+	  line (which will also disable hibernation).
 
-	   Entropy is generated using the RDRAND instruction if it is
-	   supported. If RDTSC is supported, it is used as well. If
-	   neither RDRAND nor RDTSC are supported, then randomness is
-	   read from the i8254 timer.
-
-	   The kernel will be offset by up to RANDOMIZE_BASE_MAX_OFFSET,
-	   and aligned according to PHYSICAL_ALIGN. Since the kernel is
-	   built using 2GiB addressing, and PHYSICAL_ALGIN must be at a
-	   minimum of 2MiB, only 10 bits of entropy is theoretically
-	   possible. At best, due to page table layouts, 64-bit can use
-	   9 bits of entropy and 32-bit uses 8 bits.
-
-	   If unsure, say N.
-
-config RANDOMIZE_BASE_MAX_OFFSET
-	hex "Maximum kASLR offset allowed" if EXPERT
-	depends on RANDOMIZE_BASE
-	range 0x0 0x20000000 if X86_32
-	default "0x20000000" if X86_32
-	range 0x0 0x40000000 if X86_64
-	default "0x40000000" if X86_64
-	---help---
-	  The lesser of RANDOMIZE_BASE_MAX_OFFSET and available physical
-	  memory is used to determine the maximal offset in bytes that will
-	  be applied to the kernel when kernel Address Space Layout
-	  Randomization (kASLR) is active. This must be a multiple of
-	  PHYSICAL_ALIGN.
-
-	  On 32-bit this is limited to 512MiB by page table layouts. The
-	  default is 512MiB.
-
-	  On 64-bit this is limited by how the kernel fixmap page table is
-	  positioned, so this cannot be larger than 1GiB currently. Without
-	  RANDOMIZE_BASE, there is a 512MiB to 1.5GiB split between kernel
-	  and modules. When RANDOMIZE_BASE_MAX_OFFSET is above 512MiB, the
-	  modules area will shrink to compensate, up to the current maximum
-	  1GiB to 1GiB split. The default is 1GiB.
-
-	  If unsure, leave at the default value.
+	  If unsure, say N.
 
 # Relocation on x86 needs some additional build support
 config X86_NEED_RELOCS
diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 7d86c5dd8e99..3ad71a0afa24 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -217,15 +217,13 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 	return false;
 }
 
-static unsigned long slots[CONFIG_RANDOMIZE_BASE_MAX_OFFSET /
-			   CONFIG_PHYSICAL_ALIGN];
+static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
 static unsigned long slot_max;
 
 static void slots_append(unsigned long addr)
 {
 	/* Overflowing the slots list should be impossible. */
-	if (slot_max >= CONFIG_RANDOMIZE_BASE_MAX_OFFSET /
-			CONFIG_PHYSICAL_ALIGN)
+	if (slot_max >= KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN)
 		return;
 
 	slots[slot_max++] = addr;
@@ -251,7 +249,7 @@ static void process_e820_entry(struct e820entry *entry,
 		return;
 
 	/* Ignore entries entirely above our maximum. */
-	if (entry->addr >= CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
+	if (entry->addr >= KERNEL_IMAGE_SIZE)
 		return;
 
 	/* Ignore entries entirely below our minimum. */
@@ -276,8 +274,8 @@ static void process_e820_entry(struct e820entry *entry,
 	region.size -= region.start - entry->addr;
 
 	/* Reduce maximum size to fit end of image within maximum limit. */
-	if (region.start + region.size > CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
-		region.size = CONFIG_RANDOMIZE_BASE_MAX_OFFSET - region.start;
+	if (region.start + region.size > KERNEL_IMAGE_SIZE)
+		region.size = KERNEL_IMAGE_SIZE - region.start;
 
 	/* Walk each aligned slot and check for avoided areas. */
 	for (img.start = region.start, img.size = image_size ;
diff --git a/arch/x86/include/asm/page_64_types.h b/arch/x86/include/asm/page_64_types.h
index 4928cf0d5af0..d5c2f8b40faa 100644
--- a/arch/x86/include/asm/page_64_types.h
+++ b/arch/x86/include/asm/page_64_types.h
@@ -47,12 +47,10 @@
  * are fully set up. If kernel ASLR is configured, it can extend the
  * kernel page table mapping, reducing the size of the modules area.
  */
-#define KERNEL_IMAGE_SIZE_DEFAULT      (512 * 1024 * 1024)
-#if defined(CONFIG_RANDOMIZE_BASE) && \
-	CONFIG_RANDOMIZE_BASE_MAX_OFFSET > KERNEL_IMAGE_SIZE_DEFAULT
-#define KERNEL_IMAGE_SIZE   CONFIG_RANDOMIZE_BASE_MAX_OFFSET
+#if defined(CONFIG_RANDOMIZE_BASE)
+#define KERNEL_IMAGE_SIZE	(1024 * 1024 * 1024)
 #else
-#define KERNEL_IMAGE_SIZE      KERNEL_IMAGE_SIZE_DEFAULT
+#define KERNEL_IMAGE_SIZE	(512 * 1024 * 1024)
 #endif
 
 #endif /* _ASM_X86_PAGE_64_DEFS_H */
diff --git a/arch/x86/mm/init_32.c b/arch/x86/mm/init_32.c
index bd7a9b9e2e14..f2ee42d61894 100644
--- a/arch/x86/mm/init_32.c
+++ b/arch/x86/mm/init_32.c
@@ -804,9 +804,6 @@ void __init mem_init(void)
 	BUILD_BUG_ON(VMALLOC_START			>= VMALLOC_END);
 #undef high_memory
 #undef __FIXADDR_TOP
-#ifdef CONFIG_RANDOMIZE_BASE
-	BUILD_BUG_ON(CONFIG_RANDOMIZE_BASE_MAX_OFFSET > KERNEL_IMAGE_SIZE);
-#endif
 
 #ifdef CONFIG_HIGHMEM
 	BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE	> FIXADDR_START);
-- 
2.6.3

[PATCH 3/5] x86, boot: Clean up things used by decompressors

[Kees Cook]

This rearranges the pieces needed to include the decompressor code
in misc.c. It wasn't obvious why things were there, so a comment was
added and definitions consolidated.

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

diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index e96829bdb6d2..0381e250a785 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -21,19 +21,19 @@
  * it is not safe to place pointers in static structures.
  */
 
+/* Macros used by the included decompressor code below. */
 #define STATIC		static
 
-#undef memcpy
-
 /*
- * Use a normal definition of memset() from string.c. There are already
+ * Use normal definitions of mem*() from string.c. There are already
  * included header files which expect a definition of memset() and by
  * the time we define memset macro, it is too late.
  */
+#undef memcpy
 #undef memset
 #define memzero(s, n)	memset((s), 0, (n))
 
-
+/* Functions used by the included decompressor code below. */
 static void error(char *m);
 
 /*
-- 
2.6.3

[PATCH 4/5] x86, boot: Make memcpy handle overlaps

[Kees Cook]

Two uses of memcpy (screen scrolling and ELF parsing) were handling
overlapping memory areas. While there were no explicitly noticed bugs
here (yet), it is best to fix this so that the copying will always be
safe.

Instead of making a new memmove function that might collide with other
memmove definitions in the decompressors, this just makes the compressed
boot's copy of memcpy overlap safe.

Reported-by: Yinghai Lu <yinghai@kernel.org>
Suggested-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/misc.c   |  4 +---
 arch/x86/boot/compressed/string.c | 22 ++++++++++++++++++++--
 2 files changed, 21 insertions(+), 5 deletions(-)

diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index 0381e250a785..eacc855ae08e 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -301,9 +301,7 @@ static void parse_elf(void *output)
 #else
 			dest = (void *)(phdr->p_paddr);
 #endif
-			memcpy(dest,
-			       output + phdr->p_offset,
-			       phdr->p_filesz);
+			memcpy(dest, output + phdr->p_offset, phdr->p_filesz);
 			break;
 		default: /* Ignore other PT_* */ break;
 		}
diff --git a/arch/x86/boot/compressed/string.c b/arch/x86/boot/compressed/string.c
index 00e788be1db9..1e10e40f49dd 100644
--- a/arch/x86/boot/compressed/string.c
+++ b/arch/x86/boot/compressed/string.c
@@ -1,7 +1,7 @@
 #include "../string.c"
 
 #ifdef CONFIG_X86_32
-void *memcpy(void *dest, const void *src, size_t n)
+void *__memcpy(void *dest, const void *src, size_t n)
 {
 	int d0, d1, d2;
 	asm volatile(
@@ -15,7 +15,7 @@ void *memcpy(void *dest, const void *src, size_t n)
 	return dest;
 }
 #else
-void *memcpy(void *dest, const void *src, size_t n)
+void *__memcpy(void *dest, const void *src, size_t n)
 {
 	long d0, d1, d2;
 	asm volatile(
@@ -39,3 +39,21 @@ void *memset(void *s, int c, size_t n)
 		ss[i] = c;
 	return s;
 }
+
+/*
+ * This memcpy is overlap safe (i.e. it is memmove without conflicting
+ * with other definitions of memmove from the various decompressors.
+ */
+void *memcpy(void *dest, const void *src, size_t n)
+{
+	unsigned char *d = dest;
+	const unsigned char *s = src;
+
+	if (d <= s || d - s >= n)
+		return __memcpy(dest, src, n);
+
+	while (n-- > 0)
+		d[n] = s[n];
+
+	return dest;
+}
-- 
2.6.3

[PATCH 5/5] x86, KASLR: Warn when KASLR is disabled

[Kees Cook]

If KASLR is built in but not available at run-time (either due to the
current conflict with hibernation, command-line request, or e820 parsing
failures), announce the state explicitly. To support this, a new "warn"
function is created, based on the existing "error" function.

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c |  6 +++---
 arch/x86/boot/compressed/misc.c  | 12 +++++++++---
 arch/x86/boot/compressed/misc.h  |  1 +
 3 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 3ad71a0afa24..8741a6d83bfe 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -314,12 +314,12 @@ unsigned char *choose_random_location(unsigned char *input,
 
 #ifdef CONFIG_HIBERNATION
 	if (!cmdline_find_option_bool("kaslr")) {
-		debug_putstr("KASLR disabled by default...\n");
+		warn("KASLR disabled: 'kaslr' not on cmdline (hibernation selected).");
 		goto out;
 	}
 #else
 	if (cmdline_find_option_bool("nokaslr")) {
-		debug_putstr("KASLR disabled by cmdline...\n");
+		warn("KASLR disabled: 'nokaslr' on cmdline.");
 		goto out;
 	}
 #endif
@@ -333,7 +333,7 @@ unsigned char *choose_random_location(unsigned char *input,
 	/* Walk e820 and find a random address. */
 	random_addr = find_random_addr(choice, output_size);
 	if (!random_addr) {
-		debug_putstr("KASLR could not find suitable E820 region...\n");
+		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
 	}
 
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index eacc855ae08e..c57d785ff955 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -166,11 +166,17 @@ void __puthex(unsigned long value)
 	}
 }
 
-static void error(char *x)
+void warn(char *m)
 {
 	error_putstr("\n\n");
-	error_putstr(x);
-	error_putstr("\n\n -- System halted");
+	error_putstr(m);
+	error_putstr("\n\n");
+}
+
+static void error(char *m)
+{
+	warn(m);
+	error_putstr(" -- System halted");
 
 	while (1)
 		asm("hlt");
diff --git a/arch/x86/boot/compressed/misc.h b/arch/x86/boot/compressed/misc.h
index 9887e0d4aaeb..e75f6cf9caaf 100644
--- a/arch/x86/boot/compressed/misc.h
+++ b/arch/x86/boot/compressed/misc.h
@@ -35,6 +35,7 @@ extern memptr free_mem_end_ptr;
 extern struct boot_params *boot_params;
 void __putstr(const char *s);
 void __puthex(unsigned long value);
+void warn(char *m);
 #define error_putstr(__x)  __putstr(__x)
 #define error_puthex(__x)  __puthex(__x)
 
-- 
2.6.3

Re: [PATCH 1/5] x86, KASLR: Update description for decompressor worst case size

[Borislav Petkov]

On Wed, Apr 20, 2016 at 01:55:42PM -0700, Kees Cook wrote:
...
> diff --git a/arch/x86/boot/header.S b/arch/x86/boot/header.S
> index 6236b9ec4b76..6b8f8728c1fa 100644
> --- a/arch/x86/boot/header.S
> +++ b/arch/x86/boot/header.S
> @@ -440,6 +440,93 @@ setup_data:		.quad 0			# 64-bit physical pointer to
>  
>  pref_address:		.quad LOAD_PHYSICAL_ADDR	# preferred load addr
>  
> +#
> +# Getting to provably safe in-place decompression is hard. Worst case
> +# behaviours need be analyzed. Here let's take decompressing gzip-compressed
> +# kernel as example to illustrate it:
> +#
> +# The file layout of gzip compressed kernel is as follows. For more
> +# information, please refer to RFC 1951 and RFC 1952.
> +#
> +#    magic[2]
> +#    method[1]
> +#    flags[1]
> +#    timestamp[4]
> +#    extraflags[1]
> +#    os[1]
> +#    compressed data blocks[N]
> +#    crc[4] orig_len[4]
> +#
> +# resulting in 18 bytes of non compressed data overhead.

What's "non compressed data overhead"?

Does that want to say:

"... resulting in 18 bytes overhead of uncompressed data."

perhaps?

> +#
> +# Files divided into blocks
> +# 1 bit (last block flag)
> +# 2 bits (block type)
> +#
> +# 1 block occurs every 32K -1 bytes or when there 50% compression
> +# has been achieved. The smallest block type encoding is always used.
> +#
> +# stored:
> +#    32 bits length in bytes.
> +#
> +# fixed:
> +#    magic fixed tree.
> +#    symbols.
> +#
> +# dynamic:
> +#    dynamic tree encoding.
> +#    symbols.
> +#
> +#
> +# The buffer for decompression in place is the length of the uncompressed
> +# data, plus a small amount extra to keep the algorithm safe. The
> +# compressed data is placed at the end of the buffer.  The output pointer
> +# is placed at the start of the buffer and the input pointer is placed
> +# where the compressed data starts. Problems will occur when the output
> +# pointer overruns the input pointer.
> +#
> +# The output pointer can only overrun the input pointer if the input
> +# pointer is moving faster than the output pointer.  A condition only
> +# triggered by data whose compressed form is larger than the uncompressed
> +# form.
> +#
> +# The worst case at the block level is a growth of the compressed data
> +# of 5 bytes per 32767 bytes.
> +#
> +# The worst case internal to a compressed block is very hard to figure.
> +# The worst case can at least be bounded by having one bit that represents
> +# 32764 bytes and then all of the rest of the bytes representing the very
> +# very last byte.
> +#
> +# All of which is enough to compute an amount of extra data that is required
> +# to be safe.  To avoid problems at the block level allocating 5 extra bytes
> +# per 32767 bytes of data is sufficient.  To avoid problems internal to a
> +# block adding an extra 32767 bytes (the worst case uncompressed block size)
> +# is sufficient, to ensure that in the worst case the decompressed data for
> +# block will stop the byte before the compressed data for a block begins.
> +# To avoid problems with the compressed data's meta information an extra 18
> +# bytes are needed.  Leading to the formula:
> +#
> +# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
> +#
> +# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
> +# Adding 32768 instead of 32767 just makes for round numbers.
> +# Adding the decompressor_size is necessary as it musht live after all
> +# of the data as well.  Last I measured the decompressor is about 14K.
> +# 10K of actual data and 4K of bss.

I guess reflow the paragraphs while at it, as well?

"Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
Adding 32768 instead of 32767 just makes for round numbers. Adding the
decompressor_size is necessary as it musht live after all of the data as
well. Last I measured the decompressor is about 14K. 10K of actual data
and 4K of bss."

and so on...

-- 
Regards/Gruss,
    Boris.

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

Re: [PATCH 2/5] x86, KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[Borislav Petkov]

On Wed, Apr 20, 2016 at 01:55:43PM -0700, Kees Cook wrote:
> From: Baoquan He <bhe@redhat.com>
> 
> Currently CONFIG_RANDOMIZE_BASE_MAX_OFFSET is used to limit the maximum
> offset for kernel randomization. This limit doesn't need to be a CONFIG
> since it is tied completely to KERNEL_IMAGE_SIZE, and will make no sense
> once physical and virtual offsets are randomized separately. This patch
> removes CONFIG_RANDOMIZE_BASE_MAX_OFFSET and consolidates the Kconfig
> help text.
> 
> Signed-off-by: Baoquan He <bhe@redhat.com>
> [kees: rewrote changelog, dropped KERNEL_IMAGE_SIZE_DEFAULT, rewrote help]
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  arch/x86/Kconfig                     | 72 ++++++++++++++----------------------
>  arch/x86/boot/compressed/kaslr.c     | 12 +++---
>  arch/x86/include/asm/page_64_types.h |  8 ++--
>  arch/x86/mm/init_32.c                |  3 --
>  4 files changed, 36 insertions(+), 59 deletions(-)
> 
> diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
> index 2dc18605831f..5892d549596d 100644
> --- a/arch/x86/Kconfig
> +++ b/arch/x86/Kconfig
> @@ -1932,54 +1932,38 @@ config RELOCATABLE
>  	  (CONFIG_PHYSICAL_START) is used as the minimum location.
>  
>  config RANDOMIZE_BASE
> -	bool "Randomize the address of the kernel image"
> +	bool "Randomize the address of the kernel image (KASLR)"
>  	depends on RELOCATABLE
>  	default n
>  	---help---
> -	   Randomizes the physical and virtual address at which the
> -	   kernel image is decompressed, as a security feature that
> -	   deters exploit attempts relying on knowledge of the location
> -	   of kernel internals.
> +	  In support of Kernel Address Space Layout Randomization (KASLR),
> +	  this randomizes the physical address at which the kernel image
> +	  is decompressed and the virtual address where the kernel

Just say "loaded" here.

> +	  image is mapped, as a security feature that deters exploit
> +	  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.)
> +
> +	  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,

Does that try to refer to the 1G kernel and 1G fixmap pagetable
mappings? I.e., level2_kernel_pgt and level2_fixmap_pgt in
arch/x86/kernel/head_64.S?

> 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.
> +
> +	  If CONFIG_HIBERNATE is also enabled, KASLR is disabled at boot
> +	  time. To enable it, boot with "kaslr" on the kernel command
> +	  line (which will also disable hibernation).

...

-- 
Regards/Gruss,
    Boris.

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

Re: [PATCH 2/5] x86, KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[Kees Cook]

On Thu, Apr 21, 2016 at 10:44 AM, Borislav Petkov <bp@suse.de> wrote:
> On Wed, Apr 20, 2016 at 01:55:43PM -0700, Kees Cook wrote:
>> From: Baoquan He <bhe@redhat.com>
>>
>> Currently CONFIG_RANDOMIZE_BASE_MAX_OFFSET is used to limit the maximum
>> offset for kernel randomization. This limit doesn't need to be a CONFIG
>> since it is tied completely to KERNEL_IMAGE_SIZE, and will make no sense
>> once physical and virtual offsets are randomized separately. This patch
>> removes CONFIG_RANDOMIZE_BASE_MAX_OFFSET and consolidates the Kconfig
>> help text.
>>
>> Signed-off-by: Baoquan He <bhe@redhat.com>
>> [kees: rewrote changelog, dropped KERNEL_IMAGE_SIZE_DEFAULT, rewrote help]
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>>  arch/x86/Kconfig                     | 72 ++++++++++++++----------------------
>>  arch/x86/boot/compressed/kaslr.c     | 12 +++---
>>  arch/x86/include/asm/page_64_types.h |  8 ++--
>>  arch/x86/mm/init_32.c                |  3 --
>>  4 files changed, 36 insertions(+), 59 deletions(-)
>>
>> diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
>> index 2dc18605831f..5892d549596d 100644
>> --- a/arch/x86/Kconfig
>> +++ b/arch/x86/Kconfig
>> @@ -1932,54 +1932,38 @@ config RELOCATABLE
>>         (CONFIG_PHYSICAL_START) is used as the minimum location.
>>
>>  config RANDOMIZE_BASE
>> -     bool "Randomize the address of the kernel image"
>> +     bool "Randomize the address of the kernel image (KASLR)"
>>       depends on RELOCATABLE
>>       default n
>>       ---help---
>> -        Randomizes the physical and virtual address at which the
>> -        kernel image is decompressed, as a security feature that
>> -        deters exploit attempts relying on knowledge of the location
>> -        of kernel internals.
>> +       In support of Kernel Address Space Layout Randomization (KASLR),
>> +       this randomizes the physical address at which the kernel image
>> +       is decompressed and the virtual address where the kernel
>
> Just say "loaded" here.

Okay, works for me. This will get some changes after the phys/virt is split.

>
>> +       image is mapped, as a security feature that deters exploit
>> +       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.)
>> +
>> +       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,
>
> Does that try to refer to the 1G kernel and 1G fixmap pagetable
> mappings? I.e., level2_kernel_pgt and level2_fixmap_pgt in
> arch/x86/kernel/head_64.S?

The "2GB addressing" part is in reference to:

       -mcmodel=kernel
           Generate code for the kernel code model.  The kernel runs in the
           negative 2 GB of the address space.  This model has to be used for
           Linux kernel code.

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

This ("page table layouts") really means fixmap and (lack of) identity
mappings. I was trying to remove some level of jargon at Ingo's
request, so this area got a bit vague. I'm happy to rewrite this
however people think is best.

>> +       layouts, 64-bit uses 9 bits of entropy and 32-bit uses 8 bits.
>> +
>> +       If CONFIG_HIBERNATE is also enabled, KASLR is disabled at boot
>> +       time. To enable it, boot with "kaslr" on the kernel command
>> +       line (which will also disable hibernation).
>
> ...
>
> --
> Regards/Gruss,
>     Boris.
>
> SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nürnberg)
> --

Thanks!

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

Re: [PATCH 1/5] x86, KASLR: Update description for decompressor worst case size

[Kees Cook]

On Thu, Apr 21, 2016 at 7:47 AM, Borislav Petkov <bp@suse.de> wrote:
> On Wed, Apr 20, 2016 at 01:55:42PM -0700, Kees Cook wrote:
> ...
>> diff --git a/arch/x86/boot/header.S b/arch/x86/boot/header.S
>> index 6236b9ec4b76..6b8f8728c1fa 100644
>> --- a/arch/x86/boot/header.S
>> +++ b/arch/x86/boot/header.S
>> @@ -440,6 +440,93 @@ setup_data:              .quad 0                 # 64-bit physical pointer to
>>
>>  pref_address:                .quad LOAD_PHYSICAL_ADDR        # preferred load addr
>>
>> +#
>> +# Getting to provably safe in-place decompression is hard. Worst case
>> +# behaviours need be analyzed. Here let's take decompressing gzip-compressed
>> +# kernel as example to illustrate it:
>> +#
>> +# The file layout of gzip compressed kernel is as follows. For more
>> +# information, please refer to RFC 1951 and RFC 1952.
>> +#
>> +#    magic[2]
>> +#    method[1]
>> +#    flags[1]
>> +#    timestamp[4]
>> +#    extraflags[1]
>> +#    os[1]
>> +#    compressed data blocks[N]
>> +#    crc[4] orig_len[4]
>> +#
>> +# resulting in 18 bytes of non compressed data overhead.
>
> What's "non compressed data overhead"?
>
> Does that want to say:
>
> "... resulting in 18 bytes overhead of uncompressed data."
>
> perhaps?

Yeah, that reads much more clearly. I'll change it.

>> +#
>> +# Files divided into blocks
>> +# 1 bit (last block flag)
>> +# 2 bits (block type)
>> +#
>> +# 1 block occurs every 32K -1 bytes or when there 50% compression
>> +# has been achieved. The smallest block type encoding is always used.
>> +#
>> +# stored:
>> +#    32 bits length in bytes.
>> +#
>> +# fixed:
>> +#    magic fixed tree.
>> +#    symbols.
>> +#
>> +# dynamic:
>> +#    dynamic tree encoding.
>> +#    symbols.
>> +#
>> +#
>> +# The buffer for decompression in place is the length of the uncompressed
>> +# data, plus a small amount extra to keep the algorithm safe. The
>> +# compressed data is placed at the end of the buffer.  The output pointer
>> +# is placed at the start of the buffer and the input pointer is placed
>> +# where the compressed data starts. Problems will occur when the output
>> +# pointer overruns the input pointer.
>> +#
>> +# The output pointer can only overrun the input pointer if the input
>> +# pointer is moving faster than the output pointer.  A condition only
>> +# triggered by data whose compressed form is larger than the uncompressed
>> +# form.
>> +#
>> +# The worst case at the block level is a growth of the compressed data
>> +# of 5 bytes per 32767 bytes.
>> +#
>> +# The worst case internal to a compressed block is very hard to figure.
>> +# The worst case can at least be bounded by having one bit that represents
>> +# 32764 bytes and then all of the rest of the bytes representing the very
>> +# very last byte.
>> +#
>> +# All of which is enough to compute an amount of extra data that is required
>> +# to be safe.  To avoid problems at the block level allocating 5 extra bytes
>> +# per 32767 bytes of data is sufficient.  To avoid problems internal to a
>> +# block adding an extra 32767 bytes (the worst case uncompressed block size)
>> +# is sufficient, to ensure that in the worst case the decompressed data for
>> +# block will stop the byte before the compressed data for a block begins.
>> +# To avoid problems with the compressed data's meta information an extra 18
>> +# bytes are needed.  Leading to the formula:
>> +#
>> +# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
>> +#
>> +# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
>> +# Adding 32768 instead of 32767 just makes for round numbers.
>> +# Adding the decompressor_size is necessary as it musht live after all
>> +# of the data as well.  Last I measured the decompressor is about 14K.
>> +# 10K of actual data and 4K of bss.
>
> I guess reflow the paragraphs while at it, as well?
>
> "Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
> Adding 32768 instead of 32767 just makes for round numbers. Adding the
> decompressor_size is necessary as it musht live after all of the data as
> well. Last I measured the decompressor is about 14K. 10K of actual data
> and 4K of bss."
>
> and so on...

Yeah, I'd been reflowing as I went and I went back and forth on that
one. It looked like it was a list ("Adding... Adding... Adding...") so
I'd left it, but my initial instinct matches your: it should just get
reflowed like all the rest.

I'll fix that too.

Thanks for the review!

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

Re: [PATCH 1/5] x86, KASLR: Update description for decompressor worst case size

[Baoquan He]

On 04/21/16 at 01:04pm, Kees Cook wrote:
> On Thu, Apr 21, 2016 at 7:47 AM, Borislav Petkov <bp@suse.de> wrote:
> > On Wed, Apr 20, 2016 at 01:55:42PM -0700, Kees Cook wrote:
> > ...
> > What's "non compressed data overhead"?
> >
> > Does that want to say:
> >
> > "... resulting in 18 bytes overhead of uncompressed data."
> >
> > perhaps?
> 
> Yeah, that reads much more clearly. I'll change it.
> 
> >> +#
> >> +# Files divided into blocks
> >> +# 1 bit (last block flag)
> >> +# 2 bits (block type)
> >> +#
> >> +# 1 block occurs every 32K -1 bytes or when there 50% compression
> >> +# has been achieved. The smallest block type encoding is always used.
> >> +#
> >> +# stored:
> >> +#    32 bits length in bytes.
> >> +#
> >> +# fixed:
> >> +#    magic fixed tree.
> >> +#    symbols.
> >> +#
> >> +# dynamic:
> >> +#    dynamic tree encoding.
> >> +#    symbols.
> >> +#
> >> +#
> >> +# The buffer for decompression in place is the length of the uncompressed
> >> +# data, plus a small amount extra to keep the algorithm safe. The
> >> +# compressed data is placed at the end of the buffer.  The output pointer
> >> +# is placed at the start of the buffer and the input pointer is placed
> >> +# where the compressed data starts. Problems will occur when the output
> >> +# pointer overruns the input pointer.
> >> +#
> >> +# The output pointer can only overrun the input pointer if the input
> >> +# pointer is moving faster than the output pointer.  A condition only
> >> +# triggered by data whose compressed form is larger than the uncompressed
> >> +# form.
> >> +#
> >> +# The worst case at the block level is a growth of the compressed data
> >> +# of 5 bytes per 32767 bytes.
> >> +#
> >> +# The worst case internal to a compressed block is very hard to figure.
> >> +# The worst case can at least be bounded by having one bit that represents
> >> +# 32764 bytes and then all of the rest of the bytes representing the very
> >> +# very last byte.
> >> +#
> >> +# All of which is enough to compute an amount of extra data that is required
> >> +# to be safe.  To avoid problems at the block level allocating 5 extra bytes
> >> +# per 32767 bytes of data is sufficient.  To avoid problems internal to a
> >> +# block adding an extra 32767 bytes (the worst case uncompressed block size)
> >> +# is sufficient, to ensure that in the worst case the decompressed data for
> >> +# block will stop the byte before the compressed data for a block begins.
> >> +# To avoid problems with the compressed data's meta information an extra 18
> >> +# bytes are needed.  Leading to the formula:
> >> +#
> >> +# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
> >> +#
> >> +# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
> >> +# Adding 32768 instead of 32767 just makes for round numbers.
> >> +# Adding the decompressor_size is necessary as it musht live after all
> >> +# of the data as well.  Last I measured the decompressor is about 14K.
> >> +# 10K of actual data and 4K of bss.
> >
> > I guess reflow the paragraphs while at it, as well?
> >
> > "Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
> > Adding 32768 instead of 32767 just makes for round numbers. Adding the
> > decompressor_size is necessary as it musht live after all of the data as
					   ~~must
There's a typo here, it should be 'must'. I didn't notice before. It
might be fixed when take Boris's paragraph reflowing. :)

> > well. Last I measured the decompressor is about 14K. 10K of actual data
> > and 4K of bss."
> >
> > and so on...
> 
> Yeah, I'd been reflowing as I went and I went back and forth on that
> one. It looked like it was a list ("Adding... Adding... Adding...") so
> I'd left it, but my initial instinct matches your: it should just get
> reflowed like all the rest.
> 
> I'll fix that too.
> 
> Thanks for the review!
> 
> -Kees
> 
> -- 
> Kees Cook
> Chrome OS & Brillo Security

Re: [PATCH 2/5] x86, KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[Ingo Molnar]

* Kees Cook <keescook@chromium.org> wrote:

> >> +       Since the kernel is built using 2GB addressing,
> >
> > Does that try to refer to the 1G kernel and 1G fixmap pagetable
> > mappings? I.e., level2_kernel_pgt and level2_fixmap_pgt in
> > arch/x86/kernel/head_64.S?
> 
> The "2GB addressing" part is in reference to:
> 
>        -mcmodel=kernel
>            Generate code for the kernel code model.  The kernel runs in the
>            negative 2 GB of the address space.  This model has to be used for
>            Linux kernel code.

On x86-64 this is a special GCC compiler small memory model, it is called the 
'kernel code model', which is rather generic and no 'real name' ever stuck.

Due to RIP-relative addressing and the sign-extension of 48 bit virtual addresses, 
this allows nearly as compact kernel code and (static) kernel data definitions as 
a 32-bit kernel would allow.

The (positive) 0-4GB virtual memory range has similar advantages, but is of course 
frequently used by user-space code. Negative addresses are reserved for the kernel 
only.

Thanks,

	Ingo

Re: [PATCH 1/5] x86, KASLR: Update description for decompressor worst case size

[Ingo Molnar]

* Kees Cook <keescook@chromium.org> wrote:

> +#
> +# Getting to provably safe in-place decompression is hard. Worst case
> +# behaviours need be analyzed. Here let's take decompressing gzip-compressed
> +# kernel as example to illustrate it:
> +#
> +# The file layout of gzip compressed kernel is as follows. For more
> +# information, please refer to RFC 1951 and RFC 1952.
> +#
> +#    magic[2]
> +#    method[1]
> +#    flags[1]
> +#    timestamp[4]
> +#    extraflags[1]
> +#    os[1]
> +#    compressed data blocks[N]
> +#    crc[4] orig_len[4]
> +#
> +# resulting in 18 bytes of non compressed data overhead.
> +#
> +# Files divided into blocks
> +# 1 bit (last block flag)
> +# 2 bits (block type)
> +#
> +# 1 block occurs every 32K -1 bytes or when there 50% compression
> +# has been achieved. The smallest block type encoding is always used.

Yeah, so I incorporated Boris's comments into this text, and started cleaning it 
up, but then stopped because it became increasingly more difficult as the 
formulation is ambiguous and vague in places.

I'll apply the patch as I edited it, but please let's do another pass to make this 
section actually readable. I know you didn't write it, but let's try to improve it 
nevertheless if we are moving it around, especially as we are changing and 
cleaning up this logic with subsequent patches, ok?

Here's the current text as I've edited it:

#
# Getting to provably safe in-place decompression is hard. Worst case
# behaviours need to be analyzed. Here let's take the decompression of
# a gzip-compressed kernel as example, to illustrate it:
#
# The file layout of gzip compressed kernel is:
#
#    magic[2]
#    method[1]
#    flags[1]
#    timestamp[4]
#    extraflags[1]
#    os[1]
#    compressed data blocks[N]
#    crc[4] orig_len[4]
#
# ... resulting in +18 bytes overhead of uncompressed data.
#
# (For more information, please refer to RFC 1951 and RFC 1952.)
#
# Files divided into blocks
# 1 bit (last block flag)
# 2 bits (block type)
#
# 1 block occurs every 32K -1 bytes or when there 50% compression
# has been achieved. The smallest block type encoding is always used.
#
# stored:
#    32 bits length in bytes.
#
# fixed:
#    magic fixed tree.
#    symbols.
#
# dynamic:
#    dynamic tree encoding.
#    symbols.
#
#
# The buffer for decompression in place is the length of the uncompressed
# data, plus a small amount extra to keep the algorithm safe. The
# compressed data is placed at the end of the buffer.  The output pointer
# is placed at the start of the buffer and the input pointer is placed
# where the compressed data starts. Problems will occur when the output
# pointer overruns the input pointer.
#
# The output pointer can only overrun the input pointer if the input
# pointer is moving faster than the output pointer.  A condition only
# triggered by data whose compressed form is larger than the uncompressed
# form.
#
# The worst case at the block level is a growth of the compressed data
# of 5 bytes per 32767 bytes.
#
# The worst case internal to a compressed block is very hard to figure.
# The worst case can at least be bounded by having one bit that represents
# 32764 bytes and then all of the rest of the bytes representing the very
# very last byte.
#
# All of which is enough to compute an amount of extra data that is required
# to be safe.  To avoid problems at the block level allocating 5 extra bytes
# per 32767 bytes of data is sufficient.  To avoid problems internal to a
# block adding an extra 32767 bytes (the worst case uncompressed block size)
# is sufficient, to ensure that in the worst case the decompressed data for
# block will stop the byte before the compressed data for a block begins.
# To avoid problems with the compressed data's meta information an extra 18
# bytes are needed.  Leading to the formula:
#
# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
#
# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
# Adding 32768 instead of 32767 just makes for round numbers.
# Adding the decompressor_size is necessary as it musht live after all
# of the data as well.  Last I measured the decompressor is about 14K.
# 10K of actual data and 4K of bss.
#
# Above analysis is for decompressing gzip compressed kernel only. Up to
# now 6 different decompressor are supported all together. And among them
# xz stores data in chunks and has maximum chunk of 64K. Hence safety
# margin should be updated to cover all decompressors so that we don't
# need to deal with each of them separately. Please check
# the description in lib/decompressor_xxx.c for specific information.
#
# extra_bytes = (uncompressed_size >> 12) + 65536 + 128
#
# Note that this calculation, which results in z_extract_offset (below),
# is currently generated in compressed/mkpiggy.c


The bit where I got lost is right at the beginning:

#
# Files divided into blocks
# 1 bit (last block flag)
# 2 bits (block type)
#
# 1 block occurs every 32K -1 bytes or when there 50% compression
# has been achieved. The smallest block type encoding is always used.
#

What are 'files' here? Uncompressed input? Compressed output? Also, the sentence 
is missing a verb. The second sentence too. It's unclear to me what the third 
sentence means: what is a 'smallest block type encoding' - it isn't defined nor 
obvious. (nor is the third sentence correct grammar, which makes things harder.)

We should try to make it an unambigious yet compact description that leads the 
reader through that information without unnecessary linguistic misunderstandings.

Then there are gems like:

# The worst case internal to a compressed block is very hard to figure.

... which suggests that this was a write-only sentence! ;-)

Thanks,

	Ingo

Re: [PATCH 0/5] x86, boot: clean up KASLR code (step 2)

[Ingo Molnar]

Another small request, I've been doing this to the previous patches:

  sed -i 's/x86, KASLR: /x86\/KASLR: /g'
  sed -i 's/x86, boot: /x86\/boot: /g'

Could you please apply the regular x86/subsys title format for future patches?

Thanks!

	Ingo

Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps

[Ingo Molnar]

* Kees Cook <keescook@chromium.org> wrote:

> Two uses of memcpy (screen scrolling and ELF parsing) were handling
> overlapping memory areas. While there were no explicitly noticed bugs
> here (yet), it is best to fix this so that the copying will always be
> safe.
> 
> Instead of making a new memmove function that might collide with other
> memmove definitions in the decompressors, this just makes the compressed
> boot's copy of memcpy overlap safe.
> 
> Reported-by: Yinghai Lu <yinghai@kernel.org>
> Suggested-by: Lasse Collin <lasse.collin@tukaani.org>
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  arch/x86/boot/compressed/misc.c   |  4 +---
>  arch/x86/boot/compressed/string.c | 22 ++++++++++++++++++++--
>  2 files changed, 21 insertions(+), 5 deletions(-)
> 
> diff --git a/arch/x86/boot/compressed/string.c b/arch/x86/boot/compressed/string.c
> index 00e788be1db9..1e10e40f49dd 100644
> --- a/arch/x86/boot/compressed/string.c
> +++ b/arch/x86/boot/compressed/string.c
> @@ -1,7 +1,7 @@
>  #include "../string.c"
>  
>  #ifdef CONFIG_X86_32

I've applied this patch, but could you please also do another patch that adds a 
comment block to the top of this special version of compressed/string.c, which 
explains why this file exists and what its purpose is?

Also:

+/*
+ * This memcpy is overlap safe (i.e. it is memmove without conflicting
+ * with other definitions of memmove from the various decompressors.
+ */
+void *memcpy(void *dest, const void *src, size_t n)

I'd not name it memcpy() if its semantics are not the same as the regular kernel 
memcpy() - that will only cause confusion later on.

I'd try to name it memmove() and would fix the memmove() hacks in decompressors:

 lib/decompress_unxz.c:#ifndef memmove
 lib/decompress_unxz.c:void *memmove(void *dest, const void *src, size_t size)
 lib/decompress_unxz.c: * Since we need memmove anyway, would use it as memcpy too.
 lib/decompress_unxz.c:# define memcpy memmove

any strong reason this cannot be done?

Some other decompressors seem to avoid memmove() intentionally:

 lib/decompress_bunzip2.c:                *by 256 in any case, using memmove here would
 lib/decompress_unlzo.c:          * of the buffer. This way memmove() isn't needed which
 lib/decompress_unlzo.c:                  * Use a loop to avoid memmove() dependency.

Thanks,

	Ingo

Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps

[Ingo Molnar]

* Kees Cook <keescook@chromium.org> wrote:

> Two uses of memcpy (screen scrolling and ELF parsing) were handling
> overlapping memory areas. While there were no explicitly noticed bugs
> here (yet), it is best to fix this so that the copying will always be
> safe.
> 
> Instead of making a new memmove function that might collide with other
> memmove definitions in the decompressors, this just makes the compressed
> boot's copy of memcpy overlap safe.

Btw., I changed all mentions of function calls to include a '()', i.e.:

 Subject: x86/boot: Make memcpy() handle overlaps
 From: Kees Cook <keescook@chromium.org>
 Date: Wed, 20 Apr 2016 13:55:45 -0700

 Two uses of memcpy() (screen scrolling and ELF parsing) were handling
 overlapping memory areas. While there were no explicitly noticed bugs
 here (yet), it is best to fix this so that the copying will always be
 safe.

 Instead of making a new memmove() function that might collide with other
 memmove() definitions in the decompressors, this just makes the compressed
 boot code's copy of memcpy() overlap-safe.

Please try to do this in future changelogs and patch titles, all references to 
function calls should use parentheses, and all references to variables or 
parameters should be escaped with '...' when it's not abundantly clear what they 
are - this makes for much easier reading.

So just to mention an extreme (made up) example, which of these two commit titles 
is less confusing to read:

  Change out parameter of function to buffer to avoid confusion

or:

  Change 'out' parameter of function() to 'buffer' to avoid confusion

?

I know which one I'd pick! ;-)

Thanks,

	Ingo

Re: [PATCH 2/5] x86, KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[Borislav Petkov]

On Fri, Apr 22, 2016 at 09:16:12AM +0200, Ingo Molnar wrote:
> 
> * Kees Cook <keescook@chromium.org> wrote:
> 
> > >> +       Since the kernel is built using 2GB addressing,
> > >
> > > Does that try to refer to the 1G kernel and 1G fixmap pagetable
> > > mappings? I.e., level2_kernel_pgt and level2_fixmap_pgt in
> > > arch/x86/kernel/head_64.S?
> > 
> > The "2GB addressing" part is in reference to:
> > 
> >        -mcmodel=kernel
> >            Generate code for the kernel code model.  The kernel runs in the
> >            negative 2 GB of the address space.  This model has to be used for
> >            Linux kernel code.
> 
> On x86-64 this is a special GCC compiler small memory model, it is called the 
> 'kernel code model', which is rather generic and no 'real name' ever stuck.
> 
> Due to RIP-relative addressing and the sign-extension of 48 bit virtual addresses, 
> this allows nearly as compact kernel code and (static) kernel data definitions as 
> a 32-bit kernel would allow.
> 
> The (positive) 0-4GB virtual memory range has similar advantages, but is of course 
> frequently used by user-space code. Negative addresses are reserved for the kernel 
> only.

So it wouldn't hurt to have a more detailed explanation like this one in
the text. And the 2G thing confused me maybe because it actually means
32-bit: 0x8000_0000 is 2G and is negative since the MSB is 1b. And I was
wondering: "but what about 64-bit...?"

Thanks.

-- 
Regards/Gruss,
    Boris.

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

[tip:x86/boot] x86/KASLR: Update description for decompressor worst case size

[tip-bot for Baoquan He]

Commit-ID:  4252db10559fc3d1efc1e43613254fdd220b014b
Gitweb:     http://git.kernel.org/tip/4252db10559fc3d1efc1e43613254fdd220b014b
Author:     Baoquan He <bhe@redhat.com>
AuthorDate: Wed, 20 Apr 2016 13:55:42 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 22 Apr 2016 10:00:50 +0200

x86/KASLR: Update description for decompressor worst case size

The comment that describes the analysis for the size of the decompressor
code only took gzip into account (there are currently 6 other decompressors
that could be used). The actual z_extract_offset calculation in code was
already handling the correct maximum size, but this documentation hadn't
been updated. This updates the documentation, fixes several typos, moves
the comment to header.S, updates references, and adds a note at the end
of the decompressor include list to remind us about updating the comment
in the future.

(Instead of moving the comment to mkpiggy.c, where the calculation
is currently happening, it is being moved to header.S because
the calculations in mkpiggy.c will be removed in favor of header.S
calculations in a following patch, and it seemed like overkill to move
the giant comment twice, especially when there's already reference to
z_extract_offset in header.S.)

Signed-off-by: Baoquan He <bhe@redhat.com>
[ Rewrote changelog, cleaned up comment style, moved comments around. ]
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: H.J. Lu <hjl.tools@gmail.com>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Yinghai Lu <yinghai@kernel.org>
Link: http://lkml.kernel.org/r/1461185746-8017-2-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c |  2 +-
 arch/x86/boot/compressed/misc.c  | 89 ++++------------------------------------
 arch/x86/boot/header.S           | 88 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 97 insertions(+), 82 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 9c29e78..7d86c5d 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -155,7 +155,7 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 
 	/*
 	 * Avoid the region that is unsafe to overlap during
-	 * decompression (see calculations at top of misc.c).
+	 * decompression (see calculations in ../header.S).
 	 */
 	unsafe_len = (output_size >> 12) + 32768 + 18;
 	unsafe = (unsigned long)input + input_size - unsafe_len;
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index ad8c01a..e96829b 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -14,90 +14,13 @@
 #include "misc.h"
 #include "../string.h"
 
-/* WARNING!!
- * This code is compiled with -fPIC and it is relocated dynamically
- * at run time, but no relocation processing is performed.
- * This means that it is not safe to place pointers in static structures.
- */
-
 /*
- * Getting to provable safe in place decompression is hard.
- * Worst case behaviours need to be analyzed.
- * Background information:
- *
- * The file layout is:
- *    magic[2]
- *    method[1]
- *    flags[1]
- *    timestamp[4]
- *    extraflags[1]
- *    os[1]
- *    compressed data blocks[N]
- *    crc[4] orig_len[4]
- *
- * resulting in 18 bytes of non compressed data overhead.
- *
- * Files divided into blocks
- * 1 bit (last block flag)
- * 2 bits (block type)
- *
- * 1 block occurs every 32K -1 bytes or when there 50% compression
- * has been achieved. The smallest block type encoding is always used.
- *
- * stored:
- *    32 bits length in bytes.
- *
- * fixed:
- *    magic fixed tree.
- *    symbols.
- *
- * dynamic:
- *    dynamic tree encoding.
- *    symbols.
- *
- *
- * The buffer for decompression in place is the length of the
- * uncompressed data, plus a small amount extra to keep the algorithm safe.
- * The compressed data is placed at the end of the buffer.  The output
- * pointer is placed at the start of the buffer and the input pointer
- * is placed where the compressed data starts.  Problems will occur
- * when the output pointer overruns the input pointer.
- *
- * The output pointer can only overrun the input pointer if the input
- * pointer is moving faster than the output pointer.  A condition only
- * triggered by data whose compressed form is larger than the uncompressed
- * form.
- *
- * The worst case at the block level is a growth of the compressed data
- * of 5 bytes per 32767 bytes.
- *
- * The worst case internal to a compressed block is very hard to figure.
- * The worst case can at least be boundined by having one bit that represents
- * 32764 bytes and then all of the rest of the bytes representing the very
- * very last byte.
- *
- * All of which is enough to compute an amount of extra data that is required
- * to be safe.  To avoid problems at the block level allocating 5 extra bytes
- * per 32767 bytes of data is sufficient.  To avoind problems internal to a
- * block adding an extra 32767 bytes (the worst case uncompressed block size)
- * is sufficient, to ensure that in the worst case the decompressed data for
- * block will stop the byte before the compressed data for a block begins.
- * To avoid problems with the compressed data's meta information an extra 18
- * bytes are needed.  Leading to the formula:
- *
- * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
- *
- * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
- * Adding 32768 instead of 32767 just makes for round numbers.
- * Adding the decompressor_size is necessary as it musht live after all
- * of the data as well.  Last I measured the decompressor is about 14K.
- * 10K of actual data and 4K of bss.
- *
+ * WARNING!!
+ * This code is compiled with -fPIC and it is relocated dynamically at
+ * run time, but no relocation processing is performed. This means that
+ * it is not safe to place pointers in static structures.
  */
 
-/*
- * gzip declarations
- */
 #define STATIC		static
 
 #undef memcpy
@@ -148,6 +71,10 @@ static int lines, cols;
 #ifdef CONFIG_KERNEL_LZ4
 #include "../../../../lib/decompress_unlz4.c"
 #endif
+/*
+ * NOTE: When adding a new decompressor, please update the analysis in
+ * ../header.S.
+ */
 
 static void scroll(void)
 {
diff --git a/arch/x86/boot/header.S b/arch/x86/boot/header.S
index 6236b9e..fd85b9e 100644
--- a/arch/x86/boot/header.S
+++ b/arch/x86/boot/header.S
@@ -440,6 +440,94 @@ setup_data:		.quad 0			# 64-bit physical pointer to
 
 pref_address:		.quad LOAD_PHYSICAL_ADDR	# preferred load addr
 
+#
+# Getting to provably safe in-place decompression is hard. Worst case
+# behaviours need to be analyzed. Here let's take the decompression of
+# a gzip-compressed kernel as example, to illustrate it:
+#
+# The file layout of gzip compressed kernel is:
+#
+#    magic[2]
+#    method[1]
+#    flags[1]
+#    timestamp[4]
+#    extraflags[1]
+#    os[1]
+#    compressed data blocks[N]
+#    crc[4] orig_len[4]
+#
+# ... resulting in +18 bytes overhead of uncompressed data.
+#
+# (For more information, please refer to RFC 1951 and RFC 1952.)
+#
+# Files divided into blocks
+# 1 bit (last block flag)
+# 2 bits (block type)
+#
+# 1 block occurs every 32K -1 bytes or when there 50% compression
+# has been achieved. The smallest block type encoding is always used.
+#
+# stored:
+#    32 bits length in bytes.
+#
+# fixed:
+#    magic fixed tree.
+#    symbols.
+#
+# dynamic:
+#    dynamic tree encoding.
+#    symbols.
+#
+#
+# The buffer for decompression in place is the length of the uncompressed
+# data, plus a small amount extra to keep the algorithm safe. The
+# compressed data is placed at the end of the buffer.  The output pointer
+# is placed at the start of the buffer and the input pointer is placed
+# where the compressed data starts. Problems will occur when the output
+# pointer overruns the input pointer.
+#
+# The output pointer can only overrun the input pointer if the input
+# pointer is moving faster than the output pointer.  A condition only
+# triggered by data whose compressed form is larger than the uncompressed
+# form.
+#
+# The worst case at the block level is a growth of the compressed data
+# of 5 bytes per 32767 bytes.
+#
+# The worst case internal to a compressed block is very hard to figure.
+# The worst case can at least be bounded by having one bit that represents
+# 32764 bytes and then all of the rest of the bytes representing the very
+# very last byte.
+#
+# All of which is enough to compute an amount of extra data that is required
+# to be safe.  To avoid problems at the block level allocating 5 extra bytes
+# per 32767 bytes of data is sufficient.  To avoid problems internal to a
+# block adding an extra 32767 bytes (the worst case uncompressed block size)
+# is sufficient, to ensure that in the worst case the decompressed data for
+# block will stop the byte before the compressed data for a block begins.
+# To avoid problems with the compressed data's meta information an extra 18
+# bytes are needed.  Leading to the formula:
+#
+# extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size
+#
+# Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
+# Adding 32768 instead of 32767 just makes for round numbers.
+# Adding the decompressor_size is necessary as it musht live after all
+# of the data as well.  Last I measured the decompressor is about 14K.
+# 10K of actual data and 4K of bss.
+#
+# Above analysis is for decompressing gzip compressed kernel only. Up to
+# now 6 different decompressor are supported all together. And among them
+# xz stores data in chunks and has maximum chunk of 64K. Hence safety
+# margin should be updated to cover all decompressors so that we don't
+# need to deal with each of them separately. Please check
+# the description in lib/decompressor_xxx.c for specific information.
+#
+# extra_bytes = (uncompressed_size >> 12) + 65536 + 128
+#
+# Note that this calculation, which results in z_extract_offset (below),
+# is currently generated in compressed/mkpiggy.c
+
 #define ZO_INIT_SIZE	(ZO__end - ZO_startup_32 + ZO_z_extract_offset)
 #define VO_INIT_SIZE	(VO__end - VO__text)
 #if ZO_INIT_SIZE > VO_INIT_SIZE

[tip:x86/boot] x86/KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

[tip-bot for Baoquan He]

Commit-ID:  e8581e3d67788b6b29d055fa42c6cb5b258fee64
Gitweb:     http://git.kernel.org/tip/e8581e3d67788b6b29d055fa42c6cb5b258fee64
Author:     Baoquan He <bhe@redhat.com>
AuthorDate: Wed, 20 Apr 2016 13:55:43 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 22 Apr 2016 10:00:50 +0200

x86/KASLR: Drop CONFIG_RANDOMIZE_BASE_MAX_OFFSET

Currently CONFIG_RANDOMIZE_BASE_MAX_OFFSET is used to limit the maximum
offset for kernel randomization. This limit doesn't need to be a CONFIG
since it is tied completely to KERNEL_IMAGE_SIZE, and will make no sense
once physical and virtual offsets are randomized separately. This patch
removes CONFIG_RANDOMIZE_BASE_MAX_OFFSET and consolidates the Kconfig
help text.

[kees: rewrote changelog, dropped KERNEL_IMAGE_SIZE_DEFAULT, rewrote help]
Signed-off-by: Baoquan He <bhe@redhat.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: H.J. Lu <hjl.tools@gmail.com>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Yinghai Lu <yinghai@kernel.org>
Link: http://lkml.kernel.org/r/1461185746-8017-3-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/Kconfig                     | 72 ++++++++++++++----------------------
 arch/x86/boot/compressed/kaslr.c     | 12 +++---
 arch/x86/include/asm/page_64_types.h |  8 ++--
 arch/x86/mm/init_32.c                |  3 --
 4 files changed, 36 insertions(+), 59 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 2dc18605..5892d54 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -1932,54 +1932,38 @@ config RELOCATABLE
 	  (CONFIG_PHYSICAL_START) is used as the minimum location.
 
 config RANDOMIZE_BASE
-	bool "Randomize the address of the kernel image"
+	bool "Randomize the address of the kernel image (KASLR)"
 	depends on RELOCATABLE
 	default n
 	---help---
-	   Randomizes the physical and virtual address at which the
-	   kernel image is decompressed, as a security feature that
-	   deters exploit attempts relying on knowledge of the location
-	   of kernel internals.
+	  In support of Kernel Address Space Layout Randomization (KASLR),
+	  this randomizes the physical address at which the kernel image
+	  is decompressed and the virtual address where the kernel
+	  image is mapped, as a security feature that deters exploit
+	  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.)
+
+	  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.
+
+	  If CONFIG_HIBERNATE is also enabled, KASLR is disabled at boot
+	  time. To enable it, boot with "kaslr" on the kernel command
+	  line (which will also disable hibernation).
 
-	   Entropy is generated using the RDRAND instruction if it is
-	   supported. If RDTSC is supported, it is used as well. If
-	   neither RDRAND nor RDTSC are supported, then randomness is
-	   read from the i8254 timer.
-
-	   The kernel will be offset by up to RANDOMIZE_BASE_MAX_OFFSET,
-	   and aligned according to PHYSICAL_ALIGN. Since the kernel is
-	   built using 2GiB addressing, and PHYSICAL_ALGIN must be at a
-	   minimum of 2MiB, only 10 bits of entropy is theoretically
-	   possible. At best, due to page table layouts, 64-bit can use
-	   9 bits of entropy and 32-bit uses 8 bits.
-
-	   If unsure, say N.
-
-config RANDOMIZE_BASE_MAX_OFFSET
-	hex "Maximum kASLR offset allowed" if EXPERT
-	depends on RANDOMIZE_BASE
-	range 0x0 0x20000000 if X86_32
-	default "0x20000000" if X86_32
-	range 0x0 0x40000000 if X86_64
-	default "0x40000000" if X86_64
-	---help---
-	  The lesser of RANDOMIZE_BASE_MAX_OFFSET and available physical
-	  memory is used to determine the maximal offset in bytes that will
-	  be applied to the kernel when kernel Address Space Layout
-	  Randomization (kASLR) is active. This must be a multiple of
-	  PHYSICAL_ALIGN.
-
-	  On 32-bit this is limited to 512MiB by page table layouts. The
-	  default is 512MiB.
-
-	  On 64-bit this is limited by how the kernel fixmap page table is
-	  positioned, so this cannot be larger than 1GiB currently. Without
-	  RANDOMIZE_BASE, there is a 512MiB to 1.5GiB split between kernel
-	  and modules. When RANDOMIZE_BASE_MAX_OFFSET is above 512MiB, the
-	  modules area will shrink to compensate, up to the current maximum
-	  1GiB to 1GiB split. The default is 1GiB.
-
-	  If unsure, leave at the default value.
+	  If unsure, say N.
 
 # Relocation on x86 needs some additional build support
 config X86_NEED_RELOCS
diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 7d86c5d..3ad71a0 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -217,15 +217,13 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 	return false;
 }
 
-static unsigned long slots[CONFIG_RANDOMIZE_BASE_MAX_OFFSET /
-			   CONFIG_PHYSICAL_ALIGN];
+static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
 static unsigned long slot_max;
 
 static void slots_append(unsigned long addr)
 {
 	/* Overflowing the slots list should be impossible. */
-	if (slot_max >= CONFIG_RANDOMIZE_BASE_MAX_OFFSET /
-			CONFIG_PHYSICAL_ALIGN)
+	if (slot_max >= KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN)
 		return;
 
 	slots[slot_max++] = addr;
@@ -251,7 +249,7 @@ static void process_e820_entry(struct e820entry *entry,
 		return;
 
 	/* Ignore entries entirely above our maximum. */
-	if (entry->addr >= CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
+	if (entry->addr >= KERNEL_IMAGE_SIZE)
 		return;
 
 	/* Ignore entries entirely below our minimum. */
@@ -276,8 +274,8 @@ static void process_e820_entry(struct e820entry *entry,
 	region.size -= region.start - entry->addr;
 
 	/* Reduce maximum size to fit end of image within maximum limit. */
-	if (region.start + region.size > CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
-		region.size = CONFIG_RANDOMIZE_BASE_MAX_OFFSET - region.start;
+	if (region.start + region.size > KERNEL_IMAGE_SIZE)
+		region.size = KERNEL_IMAGE_SIZE - region.start;
 
 	/* Walk each aligned slot and check for avoided areas. */
 	for (img.start = region.start, img.size = image_size ;
diff --git a/arch/x86/include/asm/page_64_types.h b/arch/x86/include/asm/page_64_types.h
index 4928cf0..d5c2f8b 100644
--- a/arch/x86/include/asm/page_64_types.h
+++ b/arch/x86/include/asm/page_64_types.h
@@ -47,12 +47,10 @@
  * are fully set up. If kernel ASLR is configured, it can extend the
  * kernel page table mapping, reducing the size of the modules area.
  */
-#define KERNEL_IMAGE_SIZE_DEFAULT      (512 * 1024 * 1024)
-#if defined(CONFIG_RANDOMIZE_BASE) && \
-	CONFIG_RANDOMIZE_BASE_MAX_OFFSET > KERNEL_IMAGE_SIZE_DEFAULT
-#define KERNEL_IMAGE_SIZE   CONFIG_RANDOMIZE_BASE_MAX_OFFSET
+#if defined(CONFIG_RANDOMIZE_BASE)
+#define KERNEL_IMAGE_SIZE	(1024 * 1024 * 1024)
 #else
-#define KERNEL_IMAGE_SIZE      KERNEL_IMAGE_SIZE_DEFAULT
+#define KERNEL_IMAGE_SIZE	(512 * 1024 * 1024)
 #endif
 
 #endif /* _ASM_X86_PAGE_64_DEFS_H */
diff --git a/arch/x86/mm/init_32.c b/arch/x86/mm/init_32.c
index bd7a9b9..f2ee42d 100644
--- a/arch/x86/mm/init_32.c
+++ b/arch/x86/mm/init_32.c
@@ -804,9 +804,6 @@ void __init mem_init(void)
 	BUILD_BUG_ON(VMALLOC_START			>= VMALLOC_END);
 #undef high_memory
 #undef __FIXADDR_TOP
-#ifdef CONFIG_RANDOMIZE_BASE
-	BUILD_BUG_ON(CONFIG_RANDOMIZE_BASE_MAX_OFFSET > KERNEL_IMAGE_SIZE);
-#endif
 
 #ifdef CONFIG_HIGHMEM
 	BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE	> FIXADDR_START);

[tip:x86/boot] x86/boot: Clean up things used by decompressors

[tip-bot for Kees Cook]

Commit-ID:  1f208de37d10bb9067f3b061d281363be0cd1805
Gitweb:     http://git.kernel.org/tip/1f208de37d10bb9067f3b061d281363be0cd1805
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Wed, 20 Apr 2016 13:55:44 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 22 Apr 2016 10:00:50 +0200

x86/boot: Clean up things used by decompressors

This rearranges the pieces needed to include the decompressor code
in misc.c. It wasn't obvious why things were there, so a comment was
added and definitions consolidated.

Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: H.J. Lu <hjl.tools@gmail.com>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Yinghai Lu <yinghai@kernel.org>
Link: http://lkml.kernel.org/r/1461185746-8017-4-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/misc.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index e96829b..0381e25 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -21,19 +21,19 @@
  * it is not safe to place pointers in static structures.
  */
 
+/* Macros used by the included decompressor code below. */
 #define STATIC		static
 
-#undef memcpy
-
 /*
- * Use a normal definition of memset() from string.c. There are already
+ * Use normal definitions of mem*() from string.c. There are already
  * included header files which expect a definition of memset() and by
  * the time we define memset macro, it is too late.
  */
+#undef memcpy
 #undef memset
 #define memzero(s, n)	memset((s), 0, (n))
 
-
+/* Functions used by the included decompressor code below. */
 static void error(char *m);
 
 /*

[tip:x86/boot] x86/boot: Make memcpy() handle overlaps

[tip-bot for Kees Cook]

Commit-ID:  bf0118dbba9542ceb5d33d4a86830a6c88b0bbf6
Gitweb:     http://git.kernel.org/tip/bf0118dbba9542ceb5d33d4a86830a6c88b0bbf6
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Wed, 20 Apr 2016 13:55:45 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 22 Apr 2016 10:00:50 +0200

x86/boot: Make memcpy() handle overlaps

Two uses of memcpy() (screen scrolling and ELF parsing) were handling
overlapping memory areas. While there were no explicitly noticed bugs
here (yet), it is best to fix this so that the copying will always be
safe.

Instead of making a new memmove() function that might collide with other
memmove() definitions in the decompressors, this just makes the compressed
boot code's copy of memcpy() overlap-safe.

Suggested-by: Lasse Collin <lasse.collin@tukaani.org>
Reported-by: Yinghai Lu <yinghai@kernel.org>
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: H.J. Lu <hjl.tools@gmail.com>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1461185746-8017-5-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/misc.c   |  4 +---
 arch/x86/boot/compressed/string.c | 22 ++++++++++++++++++++--
 2 files changed, 21 insertions(+), 5 deletions(-)

diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index 0381e25..eacc855 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -301,9 +301,7 @@ static void parse_elf(void *output)
 #else
 			dest = (void *)(phdr->p_paddr);
 #endif
-			memcpy(dest,
-			       output + phdr->p_offset,
-			       phdr->p_filesz);
+			memcpy(dest, output + phdr->p_offset, phdr->p_filesz);
 			break;
 		default: /* Ignore other PT_* */ break;
 		}
diff --git a/arch/x86/boot/compressed/string.c b/arch/x86/boot/compressed/string.c
index 00e788b..1e10e40 100644
--- a/arch/x86/boot/compressed/string.c
+++ b/arch/x86/boot/compressed/string.c
@@ -1,7 +1,7 @@
 #include "../string.c"
 
 #ifdef CONFIG_X86_32
-void *memcpy(void *dest, const void *src, size_t n)
+void *__memcpy(void *dest, const void *src, size_t n)
 {
 	int d0, d1, d2;
 	asm volatile(
@@ -15,7 +15,7 @@ void *memcpy(void *dest, const void *src, size_t n)
 	return dest;
 }
 #else
-void *memcpy(void *dest, const void *src, size_t n)
+void *__memcpy(void *dest, const void *src, size_t n)
 {
 	long d0, d1, d2;
 	asm volatile(
@@ -39,3 +39,21 @@ void *memset(void *s, int c, size_t n)
 		ss[i] = c;
 	return s;
 }
+
+/*
+ * This memcpy is overlap safe (i.e. it is memmove without conflicting
+ * with other definitions of memmove from the various decompressors.
+ */
+void *memcpy(void *dest, const void *src, size_t n)
+{
+	unsigned char *d = dest;
+	const unsigned char *s = src;
+
+	if (d <= s || d - s >= n)
+		return __memcpy(dest, src, n);
+
+	while (n-- > 0)
+		d[n] = s[n];
+
+	return dest;
+}

[tip:x86/boot] x86/KASLR: Warn when KASLR is disabled

[tip-bot for Kees Cook]

Commit-ID:  0f8ede1b8c4cb845c53072d7e49d71ca24a61ced
Gitweb:     http://git.kernel.org/tip/0f8ede1b8c4cb845c53072d7e49d71ca24a61ced
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Wed, 20 Apr 2016 13:55:46 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 22 Apr 2016 10:00:51 +0200

x86/KASLR: Warn when KASLR is disabled

If KASLR is built in but not available at run-time (either due to the
current conflict with hibernation, command-line request, or e820 parsing
failures), announce the state explicitly. To support this, a new "warn"
function is created, based on the existing "error" function.

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: H.J. Lu <hjl.tools@gmail.com>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Yinghai Lu <yinghai@kernel.org>
Link: http://lkml.kernel.org/r/1461185746-8017-6-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c |  6 +++---
 arch/x86/boot/compressed/misc.c  | 12 +++++++++---
 arch/x86/boot/compressed/misc.h  |  1 +
 3 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 3ad71a0..8741a6d 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -314,12 +314,12 @@ unsigned char *choose_random_location(unsigned char *input,
 
 #ifdef CONFIG_HIBERNATION
 	if (!cmdline_find_option_bool("kaslr")) {
-		debug_putstr("KASLR disabled by default...\n");
+		warn("KASLR disabled: 'kaslr' not on cmdline (hibernation selected).");
 		goto out;
 	}
 #else
 	if (cmdline_find_option_bool("nokaslr")) {
-		debug_putstr("KASLR disabled by cmdline...\n");
+		warn("KASLR disabled: 'nokaslr' on cmdline.");
 		goto out;
 	}
 #endif
@@ -333,7 +333,7 @@ unsigned char *choose_random_location(unsigned char *input,
 	/* Walk e820 and find a random address. */
 	random_addr = find_random_addr(choice, output_size);
 	if (!random_addr) {
-		debug_putstr("KASLR could not find suitable E820 region...\n");
+		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
 	}
 
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index eacc855..c57d785 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -166,11 +166,17 @@ void __puthex(unsigned long value)
 	}
 }
 
-static void error(char *x)
+void warn(char *m)
 {
 	error_putstr("\n\n");
-	error_putstr(x);
-	error_putstr("\n\n -- System halted");
+	error_putstr(m);
+	error_putstr("\n\n");
+}
+
+static void error(char *m)
+{
+	warn(m);
+	error_putstr(" -- System halted");
 
 	while (1)
 		asm("hlt");
diff --git a/arch/x86/boot/compressed/misc.h b/arch/x86/boot/compressed/misc.h
index 9887e0d..e75f6cf 100644
--- a/arch/x86/boot/compressed/misc.h
+++ b/arch/x86/boot/compressed/misc.h
@@ -35,6 +35,7 @@ extern memptr free_mem_end_ptr;
 extern struct boot_params *boot_params;
 void __putstr(const char *s);
 void __puthex(unsigned long value);
+void warn(char *m);
 #define error_putstr(__x)  __putstr(__x)
 #define error_puthex(__x)  __puthex(__x)
 

Re: [PATCH 0/5] x86, boot: clean up KASLR code (step 2)

[Kees Cook]

On Fri, Apr 22, 2016 at 12:43 AM, Ingo Molnar <mingo@kernel.org> wrote:
>
> Another small request, I've been doing this to the previous patches:
>
>   sed -i 's/x86, KASLR: /x86\/KASLR: /g'
>   sed -i 's/x86, boot: /x86\/boot: /g'
>
> Could you please apply the regular x86/subsys title format for future patches?

Ah! Yes, sorry. I'll use a slash from now on.

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

Re: [tip:x86/boot] x86/boot: Make memcpy() handle overlaps

[Lasse Collin]

On 2016-04-22 tip-bot for Kees Cook wrote:
> x86/boot: Make memcpy() handle overlaps
> 
> Two uses of memcpy() (screen scrolling and ELF parsing) were handling
> overlapping memory areas. While there were no explicitly noticed bugs
> here (yet), it is best to fix this so that the copying will always be
> safe.
> 
> Instead of making a new memmove() function that might collide with
> other memmove() definitions in the decompressors, this just makes the
> compressed boot code's copy of memcpy() overlap-safe.

So far lib/decompress_unxz.c is the only decompressor that needs
memmove(). There the local definition is inside #ifndef to make it easy
to omit it and to use another memmove() implementation. It's enough to
do this:

    #define memmove memmove

To me it sounds less confusing if a function that works on overlapping
buffers is named memmove() instead of memcpy(). In those places where
buffers can overlap one would then use memmove() so that it's clear to
the reader that overlapping is possible.

-- 
Lasse Collin  |  IRC: Larhzu @ IRCnet & Freenode

Re: [tip:x86/boot] x86/boot: Make memcpy() handle overlaps

[Kees Cook]

On Fri, Apr 22, 2016 at 2:05 PM, Lasse Collin <lasse.collin@tukaani.org> wrote:
> On 2016-04-22 tip-bot for Kees Cook wrote:
>> x86/boot: Make memcpy() handle overlaps
>>
>> Two uses of memcpy() (screen scrolling and ELF parsing) were handling
>> overlapping memory areas. While there were no explicitly noticed bugs
>> here (yet), it is best to fix this so that the copying will always be
>> safe.
>>
>> Instead of making a new memmove() function that might collide with
>> other memmove() definitions in the decompressors, this just makes the
>> compressed boot code's copy of memcpy() overlap-safe.
>
> So far lib/decompress_unxz.c is the only decompressor that needs
> memmove(). There the local definition is inside #ifndef to make it easy
> to omit it and to use another memmove() implementation. It's enough to
> do this:
>
>     #define memmove memmove
>
> To me it sounds less confusing if a function that works on overlapping
> buffers is named memmove() instead of memcpy(). In those places where
> buffers can overlap one would then use memmove() so that it's clear to
> the reader that overlapping is possible.

Okay, I'll refactor this and double-check the xz case.

Thanks!

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps

[Kees Cook]

On Fri, Apr 22, 2016 at 12:49 AM, Ingo Molnar <mingo@kernel.org> wrote:
>
> * Kees Cook <keescook@chromium.org> wrote:
>
>> Two uses of memcpy (screen scrolling and ELF parsing) were handling
>> overlapping memory areas. While there were no explicitly noticed bugs
>> here (yet), it is best to fix this so that the copying will always be
>> safe.
>>
>> Instead of making a new memmove function that might collide with other
>> memmove definitions in the decompressors, this just makes the compressed
>> boot's copy of memcpy overlap safe.
>>
>> Reported-by: Yinghai Lu <yinghai@kernel.org>
>> Suggested-by: Lasse Collin <lasse.collin@tukaani.org>
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>>  arch/x86/boot/compressed/misc.c   |  4 +---
>>  arch/x86/boot/compressed/string.c | 22 ++++++++++++++++++++--
>>  2 files changed, 21 insertions(+), 5 deletions(-)
>>
>> diff --git a/arch/x86/boot/compressed/string.c b/arch/x86/boot/compressed/string.c
>> index 00e788be1db9..1e10e40f49dd 100644
>> --- a/arch/x86/boot/compressed/string.c
>> +++ b/arch/x86/boot/compressed/string.c
>> @@ -1,7 +1,7 @@
>>  #include "../string.c"
>>
>>  #ifdef CONFIG_X86_32
>
> I've applied this patch, but could you please also do another patch that adds a
> comment block to the top of this special version of compressed/string.c, which
> explains why this file exists and what its purpose is?

So... this isn't exactly clearly to me. I assume that something about
the builtin memcpy doesn't work during compressed boot, so
compressed/string.c needed to explicitly overload them. If that
matches your understanding, I can add a comment to that effect.

> Also:
>
> +/*
> + * This memcpy is overlap safe (i.e. it is memmove without conflicting
> + * with other definitions of memmove from the various decompressors.
> + */
> +void *memcpy(void *dest, const void *src, size_t n)
>
> I'd not name it memcpy() if its semantics are not the same as the regular kernel
> memcpy() - that will only cause confusion later on.
>
> I'd try to name it memmove() and would fix the memmove() hacks in decompressors:
>
>  lib/decompress_unxz.c:#ifndef memmove
>  lib/decompress_unxz.c:void *memmove(void *dest, const void *src, size_t size)
>  lib/decompress_unxz.c: * Since we need memmove anyway, would use it as memcpy too.
>  lib/decompress_unxz.c:# define memcpy memmove
>
> any strong reason this cannot be done?

Lasse asked for this too, but I'm going to avoid poking at the
decompressor code and just use the interface it already defines: the
"memmove" define.

> Some other decompressors seem to avoid memmove() intentionally:
>
>  lib/decompress_bunzip2.c:                *by 256 in any case, using memmove here would
>  lib/decompress_unlzo.c:          * of the buffer. This way memmove() isn't needed which
>  lib/decompress_unlzo.c:                  * Use a loop to avoid memmove() dependency.

Yeah, seems like it's not hard to add memmove! :)

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security