Skip to contentSkip to conversation

kernel decompressor interface

DISCUSSION H. Peter Anvin 3 participants 4 messages Mar 30, 2010 – Apr 1, 2010 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 17 lines · Ferenc Wagner

Hi,

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.

However, I feel like their advantages could be combined by making the fill() and flush() callbacks able to change the buffer addresses, like int fill(void **, unsigned int) for example. Even better, some context could also be passed around, so that they can easily carry private state.

Quoted 5 lines

A cursory look at the LZMA decompressor implementation suggests that this would be straightforward change (although I haven't done it). Do you think that
1. it could be done for other decompressors (lzo, bunzip) as well, and
2. it should be done in any form (interface replacement or extension)?

I think the event-based interfaces in zlib.h are pretty good, myself, and since they are so widely deployed they are also widely mimiced, which makes it a good interface to rely on. A simpler "one shot" interface can then be implemented as a wrapper (since it just means:
create the context, point it at the two buffers, and then tell it to to run to the end.)

LZO has some super-compact variants that don't support start and stop operation, but even the "full featured" versions are small enough, that I don't think it matters for something as large as the Linux kernel. It mattered to me when I was dealing with self-decompressing objects on the order of a few tens of kilobytes.

-hpa

#2 lore raw
In reply to a message not in the archive
Quoted 12 lines · Ferenc Wagner

Hi,

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.

The decompress_fn interface is rather limited, however, it must
be borne in mind that it was adequate for the original intended users (initramfs/initrd decompression). Squashfs (and other filesystems) on the other hand can certainly make use of a much better multi-call interface. My strategy in adding LZMA support to Squashfs has been to get an implementation using the current interface mainlined, and one this has been done to look at improving the decompress_fn interface.

Quoted 7 lines

However, I feel like their advantages could be combined by making the fill() and flush() callbacks able to change the buffer addresses, like int fill(void **, unsigned int) for example. Even better, some context could also be passed around, so that they can easily carry private state.

A cursory look at the LZMA decompressor implementation suggests that this would be straightforward change (although I haven't done it).

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)

The following original thread about inclusion of LZMA into the kernel has some relevant information.

http://www.mail-archive.com/[email protected]/msg01371.html

Phillip

Quoted 4 lines

Do
you think that
1. it could be done for other decompressors (lzo, bunzip) as well, and
2. it should be done in any form (interface replacement or extension)?

#3 lore raw
Quoted 13 lines · Phillip Lougher
Quoted 11 lines · Ferenc Wagner

Hi,

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.

Quoted 7 lines

The decompress_fn interface is rather limited, however, it must
be borne in mind that it was adequate for the original intended users (initramfs/initrd decompression). Squashfs (and other filesystems) on the other hand can certainly make use of a much better multi-call interface. My strategy in adding LZMA support to Squashfs has been to get an implementation using the current interface mainlined, and one this has been done to look at improving the decompress_fn interface.

Well, it's adequate for the *current form* of initramfs decompression, which is rather crippled: we fail to progressively free the memory used, simply because we have no way to track it.

This is, in my opinion, a major shortcoming of the current implementation.

Quoted 8 lines

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

-hpa

#4 lore raw
Quoted 29 lines · H. Peter Anvin
Quoted 13 lines · Phillip Lougher
Quoted 10 lines · Ferenc Wagner

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.

Quoted 8 lines

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.

Quoted 7 lines

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.

Signature · 2 lines
Regards,
Feri.