Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1383743 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/5] x86, boot: clean up KASLR code (step 2) Kees Cook <keescook@chromium.org> - 2016-04-20 23:00 +0200
    [PATCH 4/5] x86, boot: Make memcpy handle overlaps Kees Cook <keescook@chromium.org> - 2016-04-20 23:00 +0200
      Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps Ingo Molnar <mingo@kernel.org> - 2016-04-22 10:00 +0200
      Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps Ingo Molnar <mingo@kernel.org> - 2016-04-22 10:00 +0200
        Re: [PATCH 4/5] x86, boot: Make memcpy handle overlaps Kees Cook <keescook@chromium.org> - 2016-04-23 00:20 +0200
      [tip:x86/boot] x86/boot: Make memcpy() handle overlaps tip-bot for Kees Cook <tipbot@zytor.com> - 2016-04-22 11:50 +0200
        Re: [tip:x86/boot] x86/boot: Make memcpy() handle overlaps Lasse Collin <lasse.collin@tukaani.org> - 2016-04-22 23:10 +0200
          Re: [tip:x86/boot] x86/boot: Make memcpy() handle overlaps Kees Cook <keescook@chromium.org> - 2016-04-23 00:10 +0200
    [PATCH 1/5] x86, KASLR: Update description for decompressor worst case size Kees Cook <keescook@chromium.org> - 2016-04-20 23:00 +0200
      Re: [PATCH 1/5] x86, KASLR: Update description for decompressor  worst case size Borislav Petkov <bp@suse.de> - 2016-04-21 16:50 +0200
        Re: [PATCH 1/5] x86, KASLR: Update description for decompressor worst  case size Kees Cook <keescook@chromium.org> - 2016-04-21 22:10 +0200
          Re: [PATCH 1/5] x86, KASLR: Update description for decompressor  worst case size Baoquan He <bhe@redhat.com> - 2016-04-22 05:20 +0200
      Re: [PATCH 1/5] x86, KASLR: Update description for decompressor  worst case size Ingo Molnar <mingo@kernel.org> - 2016-04-22 09:50 +0200
      [tip:x86/boot] x86/KASLR: Update description for decompressor worst  case size tip-bot for Baoquan He <tipbot@zytor.com> - 2016-04-22 11:50 +0200
    Re: [PATCH 0/5] x86, boot: clean up KASLR code (step 2) Ingo Molnar <mingo@kernel.org> - 2016-04-22 09:50 +0200
      Re: [PATCH 0/5] x86, boot: clean up KASLR code (step 2) Kees Cook <keescook@chromium.org> - 2016-04-22 17:40 +0200

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

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

[toc] | [next] | [standalone]

#1383744 — [PATCH 4/5] 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'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

[toc] | [prev] | [next] | [standalone]

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

* 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

[toc] | [prev] | [next] | [standalone]

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

* 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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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;
+}

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

* 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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

#1384747

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

[toc] | [prev] | [next] | [standalone]

#1385286

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web