Re: LZMA inclusion

[Phillip Lougher <phillip@lougher.demon.co.uk>]

Jörn Engel wrote:
> On Sat, 6 December 2008 23:56:50 +0200, Lasse Collin wrote:
>> Since you are improving the crypto API, maybe it would be a good idea to 
>> add a flag to tell the decoder that the whole output buffer will be 
>> kept available to the multi-call decoder.
> 
> I'm not convinced this is the right direction.  One of the constraints
> of kernel programming is that large contiguous are hard to come by.  The
> mm subsystem makes no guarantees that you will be able to allocate 1MiB
> or contiguous memory.  On a 32bit system with highmem, it may even
> become hard to get 1MiB from vmalloc.

This is an important issue, on the last Squashfs submission attempt, its 
  use of vmalloc to allocate up to 1MiB contiguous blocks for 
decompression was brought up.  Any LZMA implementation which requires 
1MiB vmalloced input and output buffers will probably face similar problems.

> 
> So another approach would be to ignore the one-shot debate and
> concentrate on taking a pagevec instead of a buffer (as in a void *
> pointer).  That would certainly be useful for other compressed
> filesystems and without checking the code (I forgot where the squashfs
> git tree was) I claim it should be useful for squashfs as well.

Squashfs doesn't use one-shot decoding with zlib for performance and 
memory issues.  Input data is split across buffer_heads (4 KiB or less 
per buffer_head), and calling zlib repeatedly for each separate 
buffer_head eliminates the necessary memcpy into a larger input buffer, 
eliminates the memory overhead for this buffer, and ensures only the 
first buffer_head needs to be waited on (for arrival off disk) before 
decompression starts.

Currently, as mentioned above, Squashfs decompresses into a single 
contiguous output buffer.  But, due to the linux kernel mailing list's 
dislike of vmalloc, this is being changed.  In future Squashfs will 
decompress into a sequence of 4 KiB output buffers (possibly in the page 
cache).

One-shot LZMA decoding therefore isn't going to work very well with 
future versions of Squashfs, obviously a solution (as is currently done 
with the Squashfs-LZMA patches) is to use separately allocated 
contiguous input/output buffers, and memcpy into and out of them, but 
this isn't particularly ideal.

The discussion about using the output buffer as the temporary workspace 
(as it isn't touched until after decompression is completely finished) 
will work with the current version of Squashfs, but it isn't going to 
work with later versions unless the LZMA code can be changed to work 
with a list of discontiguous output buffers (i.e. a scatter-gather type 
list).

So it looks inevitable that a separately vmalloced workspace buffer will 
be required.

Phillip

> 
> Jörn
>