About support XZ-compressed kernel on x86
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 <[email protected]> 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
Quoted 26 lines · Baoquan He
Hi Lasse,
I am checking a thread related to kaslr and
setup_dataissue on x86:
https://lkml.org/lkml/2015/7/7/963Now I have a question about the commit from you:
commit
303148045aac34b70db722a54e5ad94a3a6625c6Author: Lasse Collin <[email protected]> Date: Wed Jan 12 17:01:24 2011 -0800x86: 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 usesboot_heapinarch/x86/boot/compressed/head_64.S, andboot_heapis assigned tofree_mem_ptrwhich is used for decompression heap malloc. During this decompressio stage it's still in copied ZO space, why did you add extra 32K space toextract_offset? If you want to increase the decompression heap space shouldn't you decrease theextract_offset? Do I misunderstand anything or miss things?
Quoted 1 line
Please help answer, I really don't understand this.
Lasse, please help have a look when it's convenient to you, many thanks.
Quoted 3 lines
Thanks
Baoquan
Quoted 9 lines · On 2016-02-12 Baoquan He wrote:
Now I have a question about the commit from you:
commit
303148045aac34b70db722a54e5ad94a3a6625c6Author: Lasse Collin <[email protected]> Date: Wed Jan 12 17:01:24 2011 -0800x86: support XZ-compressed kernel
Quoted 11 lines
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 usesboot_heapinarch/x86/boot/compressed/head_64.S, andboot_heapis assigned tofree_mem_ptrwhich is used for decompression heap malloc. During this decompressio stage it's still in copied ZO space, why did you add extra 32K space toextract_offset? If you want to increase the decompression heap space shouldn't you decrease theextract_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.
Signature · 1 line
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
Quoted 22 lines · Lasse Collin
Quoted 9 lines · On 2016-02-12 Baoquan He wrote:
Now I have a question about the commit from you:
commit
303148045aac34b70db722a54e5ad94a3a6625c6Author: Lasse Collin <[email protected]> Date: Wed Jan 12 17:01:24 2011 -0800x86: support XZ-compressed kernel
Quoted 11 lines
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 usesboot_heapinarch/x86/boot/compressed/head_64.S, andboot_heapis assigned tofree_mem_ptrwhich is used for decompression heap malloc. During this decompressio stage it's still in copied ZO space, why did you add extra 32K space toextract_offset? If you want to increase the decompression heap space shouldn't you decrease theextract_offset? Do I misunderstand anything or miss things?
Quoted 7 lines
The reason to increase the heap size in
arch/x86/include/asm/boot.his unrelated to the reason why the offset was changed inarch/x86/boot/compressed/mkpiggy.c.The long comment in
arch/x86/boot/compressed/misc.cexplains the need for the offset for gzip/Deflate. A similar comment inlib/decompress_unxz.cexplains 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
Quoted 4 lines
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.
Quoted 5 lines · On 2016-02-14 Baoquan He wrote:
Quoted 3 lines · Lasse Collin
The long comment in
arch/x86/boot/compressed/misc.cexplains the need for the offset for gzip/Deflate. A similar comment inlib/decompress_unxz.cexplains it for XZ/LZMA2.
Quoted 7 lines
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.cis 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.
Signature · 1 line
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
Quoted 14 lines · Lasse Collin
Quoted 5 lines · On 2016-02-14 Baoquan He wrote:
Quoted 3 lines · Lasse Collin
The long comment in
arch/x86/boot/compressed/misc.cexplains the need for the offset for gzip/Deflate. A similar comment inlib/decompress_unxz.cexplains it for XZ/LZMA2.Quoted 7 lines
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.cis 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?
Quoted 1 line
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
Quoted 29 lines
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 dataStart: FFFFFFFFFFFFFFCCCCCCCC
Decompressing: KKKKKKKKKKFFFFFFFFCCCC
Finished: KKKKKKKKKKKKKKKKKKKKFFThe 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: KKKKKKKKKKKKKKKKKKKKFFThe safety margin ensures that the write position can never overtake the read position.
Signature · 1 line
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
Quoted 8 lines · On 2016-02-16 Baoquan He wrote:
Quoted 2 lines · Lasse Collin
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.
Signature · 1 line
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
Quoted 5 lines · Lasse Collin
Quoted 4 lines · On 2016-02-16 Baoquan He wrote:
Quoted 2 lines · Lasse Collin
Yes, like all zeros. I wrote another explanation just in case it helps:
Quoted 7 lines
Quoted 4 lines
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
Quoted 3 lines
Signature · 2 lines
-- Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
Quoted 11 lines · 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.
Signature · 1 line
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode