About support XZ-compressed kernel on x86

About support XZ-compressed kernel on x86

[Baoquan He]

Hi Lasse,

I am checking a thread related to kaslr and setup_data issue on x86:
https://lkml.org/lkml/2015/7/7/963

Now I have a question about the commit from you:

commit 303148045aac34b70db722a54e5ad94a3a6625c6
Author: Lasse Collin <lasse.collin@tukaani.org>
Date:   Wed Jan 12 17:01:24 2011 -0800

    x86: support XZ-compressed kernel


In this commit for adding support of XZ-compressed kernel on x86, you
add extra 32K to the extract_offset. In commit log you said this is
because "The XZ decompressor needs around 30 KiB of heap, so the heap
size is increased to 32 KiB on both x86-32 and x86-64." With my
understanding decompression is done in decompression stage and it uses
boot_heap in arch/x86/boot/compressed/head_64.S, and boot_heap is
assigned to free_mem_ptr which is used for decompression heap malloc.
During this decompressio stage it's still in copied ZO space, why did
you add extra 32K space to extract_offset?  If you want to increase the
decompression heap space shouldn't you decrease the extract_offset? Do I
misunderstand anything or miss things?

Please help answer, I really don't understand this.

Thanks
Baoquan

Re: About support XZ-compressed kernel on x86

[Baoquan He]

On 02/12/16 at 11:34pm, Baoquan He wrote:
> Hi Lasse,
> 
> I am checking a thread related to kaslr and setup_data issue on x86:
> https://lkml.org/lkml/2015/7/7/963
> 
> Now I have a question about the commit from you:
> 
> commit 303148045aac34b70db722a54e5ad94a3a6625c6
> Author: Lasse Collin <lasse.collin@tukaani.org>
> Date:   Wed Jan 12 17:01:24 2011 -0800
> 
>     x86: support XZ-compressed kernel
> 
> 
> In this commit for adding support of XZ-compressed kernel on x86, you
> add extra 32K to the extract_offset. In commit log you said this is
> because "The XZ decompressor needs around 30 KiB of heap, so the heap
> size is increased to 32 KiB on both x86-32 and x86-64." With my
> understanding decompression is done in decompression stage and it uses
> boot_heap in arch/x86/boot/compressed/head_64.S, and boot_heap is
> assigned to free_mem_ptr which is used for decompression heap malloc.
> During this decompressio stage it's still in copied ZO space, why did
> you add extra 32K space to extract_offset?  If you want to increase the
> decompression heap space shouldn't you decrease the extract_offset? Do I
> misunderstand anything or miss things?
> 
> Please help answer, I really don't understand this.

Lasse, please help have a look when it's convenient to you, many thanks.

> 
> Thanks
> Baoquan

Re: About support XZ-compressed kernel on x86

[Lasse Collin]

On 2016-02-12 Baoquan He wrote:
> Now I have a question about the commit from you:
> 
> commit 303148045aac34b70db722a54e5ad94a3a6625c6
> Author: Lasse Collin <lasse.collin@tukaani.org>
> Date:   Wed Jan 12 17:01:24 2011 -0800
> 
>     x86: support XZ-compressed kernel
> 
> 
> In this commit for adding support of XZ-compressed kernel on x86, you
> add extra 32K to the extract_offset. In commit log you said this is
> because "The XZ decompressor needs around 30 KiB of heap, so the heap
> size is increased to 32 KiB on both x86-32 and x86-64." With my
> understanding decompression is done in decompression stage and it uses
> boot_heap in arch/x86/boot/compressed/head_64.S, and boot_heap is
> assigned to free_mem_ptr which is used for decompression heap malloc.
> During this decompressio stage it's still in copied ZO space, why did
> you add extra 32K space to extract_offset?  If you want to increase
> the decompression heap space shouldn't you decrease the
> extract_offset? Do I misunderstand anything or miss things?

The reason to increase the heap size in arch/x86/include/asm/boot.h is
unrelated to the reason why the offset was changed in
arch/x86/boot/compressed/mkpiggy.c.

The long comment in arch/x86/boot/compressed/misc.c explains the need
for the offset for gzip/Deflate. A similar comment in
lib/decompress_unxz.c explains it for XZ/LZMA2.

Smaller safety-margins can work in practice since the calculated
margins are for the worst case. I'm not even sure if such calculations
have been done for the other decompressors in Linux.

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

Re: About support XZ-compressed kernel on x86

[Baoquan He]

On 02/13/16 at 08:57pm, Lasse Collin wrote:
> On 2016-02-12 Baoquan He wrote:
> > Now I have a question about the commit from you:
> > 
> > commit 303148045aac34b70db722a54e5ad94a3a6625c6
> > Author: Lasse Collin <lasse.collin@tukaani.org>
> > Date:   Wed Jan 12 17:01:24 2011 -0800
> > 
> >     x86: support XZ-compressed kernel
> > 
> > 
> > In this commit for adding support of XZ-compressed kernel on x86, you
> > add extra 32K to the extract_offset. In commit log you said this is
> > because "The XZ decompressor needs around 30 KiB of heap, so the heap
> > size is increased to 32 KiB on both x86-32 and x86-64." With my
> > understanding decompression is done in decompression stage and it uses
> > boot_heap in arch/x86/boot/compressed/head_64.S, and boot_heap is
> > assigned to free_mem_ptr which is used for decompression heap malloc.
> > During this decompressio stage it's still in copied ZO space, why did
> > you add extra 32K space to extract_offset?  If you want to increase
> > the decompression heap space shouldn't you decrease the
> > extract_offset? Do I misunderstand anything or miss things?
> 
> The reason to increase the heap size in arch/x86/include/asm/boot.h is
> unrelated to the reason why the offset was changed in
> arch/x86/boot/compressed/mkpiggy.c.
> 
> The long comment in arch/x86/boot/compressed/misc.c explains the need
> for the offset for gzip/Deflate. A similar comment in
> lib/decompress_unxz.c explains it for XZ/LZMA2.

Thank you so much, Lasse. You clearly pointed out my confusion.
Yeah, I didn't understand it well. Your description for xz in
lib/decompress_unxz.c is very helpful. The 64K is the maximum payload in
one chunk. Adding this 64K is to avoid the worst case that very small
payload can reprsent a 64K uncompressed output data. With my
understanding it could be  a chunk which contains complete duplicate
content. like all "0" or other stuff?

Thanks
Baoquan

> 
> Smaller safety-margins can work in practice since the calculated
> margins are for the worst case. I'm not even sure if such calculations
> have been done for the other decompressors in Linux.

Re: About support XZ-compressed kernel on x86

[Lasse Collin]

On 2016-02-14 Baoquan He wrote:
> On 02/13/16 at 08:57pm, Lasse Collin wrote:
> > The long comment in arch/x86/boot/compressed/misc.c explains the
> > need for the offset for gzip/Deflate. A similar comment in
> > lib/decompress_unxz.c explains it for XZ/LZMA2.  
> 
> Thank you so much, Lasse. You clearly pointed out my confusion.
> Yeah, I didn't understand it well. Your description for xz in
> lib/decompress_unxz.c is very helpful. The 64K is the maximum payload
> in one chunk. Adding this 64K is to avoid the worst case that very
> small payload can reprsent a 64K uncompressed output data. With my
> understanding it could be  a chunk which contains complete duplicate
> content. like all "0" or other stuff?

Yes, like all zeros. I wrote another explanation just in case it helps:

In-place decompression puts the compressed data at the end of the
buffer and decompresses it to the beginning of the buffer:

    F = free memory
    K = uncompressed kernel
    C = compressed input data

    Start:         FFFFFFFFFFFFFFCCCCCCCC
    Decompressing: KKKKKKKKKKFFFFFFFFCCCC
    Finished:      KKKKKKKKKKKKKKKKKKKKFF

The free memory (FF) at the end is the safety margin.

In the worst case the beginning of the uncompressed data compresses to
almost nothing (like all zeros do), and the end of the data is
incompressible. In the beginning the write position of the decompressor
advances quickly while the read position moves very little, and thus
the write position quickly approaches the read position:

    Start:         FFFFFFFFFFFFFFCCCCCCCC
    Decompressing: KKKKKKKKKKKKKKFCCCCCCC
    Finished:      KKKKKKKKKKKKKKKKKKKKFF

The safety margin ensures that the write position can never overtake
the read position.

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

Re: About support XZ-compressed kernel on x86

[Baoquan He]

On 02/15/16 at 10:26pm, Lasse Collin wrote:
> On 2016-02-14 Baoquan He wrote:
> > On 02/13/16 at 08:57pm, Lasse Collin wrote:
> > > The long comment in arch/x86/boot/compressed/misc.c explains the
> > > need for the offset for gzip/Deflate. A similar comment in
> > > lib/decompress_unxz.c explains it for XZ/LZMA2.  
> > 
> > Thank you so much, Lasse. You clearly pointed out my confusion.
> > Yeah, I didn't understand it well. Your description for xz in
> > lib/decompress_unxz.c is very helpful. The 64K is the maximum payload
> > in one chunk. Adding this 64K is to avoid the worst case that very
> > small payload can reprsent a 64K uncompressed output data. With my
> > understanding it could be  a chunk which contains complete duplicate
> > content. like all "0" or other stuff?
> 
> Yes, like all zeros. I wrote another explanation just in case it helps:

Yes, this is great and very helpful for people who want to understand
this details. I want to make some change to improve the readability of
the description in boot/compressed/misc.c, do you mind if I put these
there? Or you can post a patch to adjust it.

Thanks
Baoquan

> 
> In-place decompression puts the compressed data at the end of the
> buffer and decompresses it to the beginning of the buffer:
> 
>     F = free memory
>     K = uncompressed kernel
>     C = compressed input data
> 
>     Start:         FFFFFFFFFFFFFFCCCCCCCC
>     Decompressing: KKKKKKKKKKFFFFFFFFCCCC
>     Finished:      KKKKKKKKKKKKKKKKKKKKFF
> 
> The free memory (FF) at the end is the safety margin.
> 
> In the worst case the beginning of the uncompressed data compresses to
> almost nothing (like all zeros do), and the end of the data is
> incompressible. In the beginning the write position of the decompressor
> advances quickly while the read position moves very little, and thus
> the write position quickly approaches the read position:
> 
>     Start:         FFFFFFFFFFFFFFCCCCCCCC
>     Decompressing: KKKKKKKKKKKKKKFCCCCCCC
>     Finished:      KKKKKKKKKKKKKKKKKKKKFF
> 
> The safety margin ensures that the write position can never overtake
> the read position.
> 
> -- 
> Lasse Collin  |  IRC: Larhzu @ IRCnet & Freenode

Re: About support XZ-compressed kernel on x86

[Lasse Collin]

On 2016-02-16 Baoquan He wrote:
> On 02/15/16 at 10:26pm, Lasse Collin wrote:
> > Yes, like all zeros. I wrote another explanation just in case it
> > helps:  
> 
> Yes, this is great and very helpful for people who want to understand
> this details. I want to make some change to improve the readability of
> the description in boot/compressed/misc.c, do you mind if I put these
> there? Or you can post a patch to adjust it.

It's fine for me if you want to do it, although I think the current
description there is quite good already.

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

Re: About support XZ-compressed kernel on x86

[Baoquan He]

On 02/17/16 at 07:57pm, Lasse Collin wrote:
> On 2016-02-16 Baoquan He wrote:
> > On 02/15/16 at 10:26pm, Lasse Collin wrote:
> > > Yes, like all zeros. I wrote another explanation just in case it
> > > helps:  
> > 
> > Yes, this is great and very helpful for people who want to understand
> > this details. I want to make some change to improve the readability of
> > the description in boot/compressed/misc.c, do you mind if I put these
> > there? Or you can post a patch to adjust it.
> 
> It's fine for me if you want to do it, although I think the current
> description there is quite good already.

OK. I still don't understand below snippet taken from misc.c. As you
said overwriting happened when the write position quickly approaches the
read position. how could it happpen if the input pointer is moving
faster than the output 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.

Thanks
Baoquan

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

Re: About support XZ-compressed kernel on x86

[Lasse Collin]

On 2016-02-18 Baoquan He wrote:
> OK. I still don't understand below snippet taken from misc.c. As you
> said overwriting happened when the write position quickly approaches
> the read position. how could it happpen if the input pointer is moving
> faster than the output 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.

That paragraph is confusing, I agree. Here is a slightly clearer
wording:

 * The output pointer can only overrun the input pointer if, at some
 * point in the decompression process, the input pointer is moving
 * faster than the output pointer.  This condition can only be
 * triggered by data whose compressed form is larger than the
 * uncompressed form.

I'm afraid it's still not good enough.

Example: Imagine a decompressor whose decompressor loop, on each
iteration, first reads exactly one input byte and then writes at least
one output byte, until all the data has been decompressed. In this case
the input pointer never moves faster than the output pointer (they can
move at the same speed though).

This kind of decompressor would need no safety margin for in-place
decompression: After reading the last input byte, the decompressor
would write one or more output bytes of which the last one would be at
the same position as the last input byte was. If the output pointer
overtook the input pointer at any point, the last input byte would make
the decompressor write past the end of the buffer. That is, the output
pointer overtaking the input pointer would be a clear sign that the
input file is corrupt: Since the input pointer cannot move faster than
the output pointer, the input pointer cannot catch up with the output
pointer so that the last output byte wouldn't be written past the end
of the buffer.

I hope the above example is clear enough; I'm not able to word it
better right now. I don't recommend putting the above example in
misc.c, but maybe the example helps in figuring out a better wording
for the existing text in misc.c.

In most decompressors, the input pointer moves faster than the output
pointer in certain common situations (like file format headers), thus
some decompressor-specific safety margin is needed.

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