linux-kernel - Re: kernel decompressor interface

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <87k4srv0cx.fsf@tac.ki.iif.hu>
Date:	Thu, 01 Apr 2010 14:11:26 +0200
From:	Ferenc Wagner <wferi@...f.hu>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	Phillip Lougher <phillip@...gher.demon.co.uk>,
	Alain Knaff <alain@...ff.lu>, linux-kernel@...r.kernel.org
Subject: Re: kernel decompressor interface

"H. Peter Anvin" <hpa@...or.com> writes:

> On 03/30/2010 05:25 PM, Phillip Lougher wrote:
>
>> Ferenc Wagner wrote:
>>
>>>
>>> While  working with SquashFS code recently, I got the impression that the
>>> current decompress_fn interface isn't best suited for general use: it
>>> rules out real scatter/gather operation, which -- one hopes -- is a
>>> general feature of stream decompressors.  For example, if one has to
>>> decompress data from a series of buffer_heads into a bunch of (cache)
>>> pages (typical operation in compressed file systems), the inflate
>>> interface in zlib.h provides the possibility of changing input and
>>> output buffer addresses, but decompress_fn does not, necessitating extra
>>> memory copying.  On the other hand, the latter is admittedly simpler.
>> 
>> LZMA decompressors have a quirk in that they use the output buffer
>> as the history buffer (e.g. look for peek_old_byte() in decompress_unlzma.c).
>> This means any multi-call interface such as zlib which modifies the output
>> buffer pointer dynamically (without allowing the decompressor to look back at
>> previously passed in buffers) won't work.   A multi-call interface that
>> passes the output buffers in an iovec style array should work though
>> (incidentally this is why Squashfs passes the output buffers as an array
>> to the decompressor wrapper even though LZMA cannot as yet make use of it)
>
> inflate has exactly the same behavior, except for the fact that the
> standard zlib implementation maintains this state internally instead of
> relying on being able to peek in the output buffer.  It's thus not an
> inherent property of the compression algorithm.
>
> The requirement that the output can't be processed incrementally is
> another major disadvantage, which I'm not sure how to address (LZMA
> requires insane amounts of memory if you don't let it use its output as
> its look-behind buffer, which means that either for small or large
> outputs we're wasting tons of memory -- in the former case with a
> separate buffer and in the latter case with a "decompress all at once"
> buffer.)

I guess this would indeed be a very welcome feature during unpacking the
initramfs.  Does the current algorithm require at least twice the
uncompressed size plus the compressed size, or is the compressed image
discarded before the cpio extraction begins?  (Streamed output is not an
issue for SquashFS right now, as it populates a block's worth of
pagecache pages in one go.)

More to the point, the memory requirement of LZMA decompression is
dominated by the dictionary size.  That's available for the decompressor
together with the uncompressed size, so if asked for streamed output it
could fall back to the one-go method if that requires less memory.
At the price of keeping the code of both algorithms around.
-- 
Regards,
Feri.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/