LZMA inclusion

LZMA inclusion

[Gregers Petersen]

Hello

There was a small talk a few days ago involving a few of the OpenWrt
developers and David Woodhouse. One of the topics discussed, was a
question about the potential of including LZMA in the kernel.
Such an inclusion would be quite benefitial in terms of embedded
systems, but the major hurdle seems to be the code quality of LZMA itself.
This leads to the question I would like to raise; are there ongoing
plans (or considerations) to rewrite and merge LZMA, and has anyone
started working on it in practical terms?

Sincerely

-- 
Gregers Petersen
People-stuff, layer 8 and anthropology
glp on irc

   _______                     ________        __
  |       |.-----.-----.-----.|  |  |  |.----.|  |_
  |   -   ||  _  |  -__|     ||  |  |  ||   _||   _|
  |_______||   __|_____|__|__||________||__|  |____|
           |__| W I R E L E S S   F R E E D O M
  KAMIKAZE (bleeding edge) -----------------------
   * 10 oz Vodka       Shake well with ice and strain
   * 10 oz Triple sec  mixture into 10 shot glasses.
   * 10 oz lime juice  Salute!
  ---------------------------------------------------

Re: LZMA inclusion

[Tim Bird]

Gregers Petersen wrote:
> There was a small talk a few days ago involving a few of the OpenWrt
> developers and David Woodhouse. One of the topics discussed, was a
> question about the potential of including LZMA in the kernel.
> Such an inclusion would be quite benefitial in terms of embedded
> systems, but the major hurdle seems to be the code quality of LZMA itself.
> This leads to the question I would like to raise; are there ongoing
> plans (or considerations) to rewrite and merge LZMA, and has anyone
> started working on it in practical terms?

Did anyone answer this?  CELF is currently considering funding
a project to do this (add LZMA support to the kernel), and
it would be good to get a feel for the current status...
 -- Tim

=============================
Tim Bird
Architecture Group Chair, CE Linux Forum
Senior Staff Engineer, Sony Corporation of America
=============================

Re: LZMA inclusion

[Florian Fainelli]

Hi Gregers, Tim,

Le Wednesday 03 December 2008 20:36:45 Tim Bird, vous avez écrit :

> Did anyone answer this?  CELF is currently considering funding
> a project to do this (add LZMA support to the kernel), and
> it would be good to get a feel for the current status...

There has been an effort for x86 to have kernels compressed using bzip2 or 
lzma [1]. The LZMA decompression code in lib/ and could be used by other 
architectures as well.

[1] http://lkml.org/lkml/2008/9/6/165
-- 
Best regards, Florian Fainelli
Email : florian@openwrt.org
http://openwrt.org
-------------------------------

Re: LZMA inclusion

[Bernhard Reutner-Fischer]

On Wed, Dec 03, 2008 at 11:36:45AM -0800, Tim Bird wrote:
>Gregers Petersen wrote:
>> There was a small talk a few days ago involving a few of the OpenWrt
>> developers and David Woodhouse. One of the topics discussed, was a
>> question about the potential of including LZMA in the kernel.
>> Such an inclusion would be quite benefitial in terms of embedded
>> systems, but the major hurdle seems to be the code quality of LZMA itself.
>> This leads to the question I would like to raise; are there ongoing
>> plans (or considerations) to rewrite and merge LZMA, and has anyone
>> started working on it in practical terms?
>
>Did anyone answer this?  CELF is currently considering funding
>a project to do this (add LZMA support to the kernel), and
>it would be good to get a feel for the current status...
> -- Tim

AFAIK xz will be/is incompatible with this older LZMA, perhaps
larhzu wants to chime in on that.

PS: A previous incarnation of that patch didn't work conventiently
for me, i had to do some small adjustments to the way it was put
into the kernel configury, like
http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-002-lzma-vmlinuz.01.patch;hb=HEAD
http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-003-lzma-vmlinuz.patch;hb=HEAD

Re: LZMA inclusion

[Gregers Petersen]

Tim Bird wrote:
> Gregers Petersen wrote:
>> There was a small talk a few days ago involving a few of the OpenWrt
>> developers and David Woodhouse. One of the topics discussed, was a
>> question about the potential of including LZMA in the kernel.
>> Such an inclusion would be quite benefitial in terms of embedded
>> systems, but the major hurdle seems to be the code quality of LZMA itself.
>> This leads to the question I would like to raise; are there ongoing
>> plans (or considerations) to rewrite and merge LZMA, and has anyone
>> started working on it in practical terms?
> 
> Did anyone answer this?  CELF is currently considering funding
> a project to do this (add LZMA support to the kernel), and
> it would be good to get a feel for the current status...
>  -- Tim
> 

I actually had one direct reply, in relationship to this project:

http://tukaani.org/

The tukaani work seems to be quite work-in-progress/alpha, but there is
progress. If such a project is to be funded it would probably be a good
idea to several partners involved (also due to the fact that it would
benifit the community as a whole).

Chz


-- 
Gregers Petersen
People-stuff, layer 8 and anthropology
glp on irc

  _______                     ________        __
 |       |.-----.-----.-----.|  |  |  |.----.|  |_
 |   -   ||  _  |  -__|     ||  |  |  ||   _||   _|
 |_______||   __|_____|__|__||________||__|  |____|
          |__| W I R E L E S S   F R E E D O M
 KAMIKAZE (bleeding edge) -----------------------
  * 10 oz Vodka       Shake well with ice and strain
  * 10 oz Triple sec  mixture into 10 shot glasses.
  * 10 oz lime juice  Salute!
 ---------------------------------------------------

Re: LZMA inclusion

[Sam Ravnborg]

On Wed, Dec 03, 2008 at 08:58:52PM +0100, Bernhard Reutner-Fischer wrote:
> On Wed, Dec 03, 2008 at 11:36:45AM -0800, Tim Bird wrote:
> >Gregers Petersen wrote:
> >> There was a small talk a few days ago involving a few of the OpenWrt
> >> developers and David Woodhouse. One of the topics discussed, was a
> >> question about the potential of including LZMA in the kernel.
> >> Such an inclusion would be quite benefitial in terms of embedded
> >> systems, but the major hurdle seems to be the code quality of LZMA itself.
> >> This leads to the question I would like to raise; are there ongoing
> >> plans (or considerations) to rewrite and merge LZMA, and has anyone
> >> started working on it in practical terms?
> >
> >Did anyone answer this?  CELF is currently considering funding
> >a project to do this (add LZMA support to the kernel), and
> >it would be good to get a feel for the current status...
> > -- Tim
> 
> AFAIK xz will be/is incompatible with this older LZMA, perhaps
> larhzu wants to chime in on that.
> 
> PS: A previous incarnation of that patch didn't work conventiently
> for me, i had to do some small adjustments to the way it was put
> into the kernel configury, like
> http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-002-lzma-vmlinuz.01.patch;hb=HEAD
> http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-003-lzma-vmlinuz.patch;hb=HEAD

If these are required with latest kernel could I then ask you to
properly submit them to: linux-kbuild@vger.kernel.org

No need to have good patches sitting at random places.

	Sam

Re: LZMA inclusion

[Bernhard Reutner-Fischer]

On Wed, Dec 03, 2008 at 09:20:09PM +0100, Sam Ravnborg wrote:
>On Wed, Dec 03, 2008 at 08:58:52PM +0100, Bernhard Reutner-Fischer wrote:
>> On Wed, Dec 03, 2008 at 11:36:45AM -0800, Tim Bird wrote:
>> >Gregers Petersen wrote:
>> >> There was a small talk a few days ago involving a few of the OpenWrt
>> >> developers and David Woodhouse. One of the topics discussed, was a
>> >> question about the potential of including LZMA in the kernel.
>> >> Such an inclusion would be quite benefitial in terms of embedded
>> >> systems, but the major hurdle seems to be the code quality of LZMA itself.
>> >> This leads to the question I would like to raise; are there ongoing
>> >> plans (or considerations) to rewrite and merge LZMA, and has anyone
>> >> started working on it in practical terms?
>> >
>> >Did anyone answer this?  CELF is currently considering funding
>> >a project to do this (add LZMA support to the kernel), and
>> >it would be good to get a feel for the current status...
>> > -- Tim
>> 
>> AFAIK xz will be/is incompatible with this older LZMA, perhaps
>> larhzu wants to chime in on that.
>> 
>> PS: A previous incarnation of that patch didn't work conventiently
>> for me, i had to do some small adjustments to the way it was put
>> into the kernel configury, like
>> http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-002-lzma-vmlinuz.01.patch;hb=HEAD
>> http://repo.or.cz/w/buildroot.git?a=blob_plain;f=toolchain/kernel-headers/lzma/linux-2.6.22.1-003-lzma-vmlinuz.patch;hb=HEAD
>
>If these are required with latest kernel could I then ask you to
>properly submit them to: linux-kbuild@vger.kernel.org

AFAIK neither lzma nor xz support was accepted yet and i did not look
if those patchlets are still required for the currently proposed
xz or lzma support.
>
>No need to have good patches sitting at random places.

Of course not, agree. I certainly don't fancy accumulating random
patches for my own personal use, at any rate.

PS: Not sure if you, Sam, are the right person who cares for it, but
i think that the help-text and actual accepted arguments of
scripts/kconfig/lxdialog/check-lxdialog.sh are out of sync.


PPS: I did not verify if this is still the case, but I have this
comment as a reminder for a small issue with "archprepare" versus
headers_install, fwiw. It would be very handy if i could fuse those
two into a simple "make ... archprepare headers_install":
        # some arches need archprepare
        # FIXME: WTH! archprepare does not honour INSTALL_HDR_PATH
        -(cd $(LINUX_HEADERS_UNPACK_DIR); \
         $(MAKE) ARCH=$(KERNEL_ARCH) \
                HOSTCC="$(HOSTCC)" HOSTCFLAGS="$(HOSTCFLAGS)" \
                HOSTCXX="$(HOSTCXX)" \
                KCONFIG_CONFIG="$(LINUX_HEADERS_DIR)/.config" \
                INSTALL_HDR_PATH=$(LINUX_HEADERS_DIR) \
                archprepare \
        )
        (cd $(LINUX_HEADERS_UNPACK_DIR); \
         $(MAKE) ARCH=$(KERNEL_ARCH) \
                HOSTCC="$(HOSTCC)" HOSTCFLAGS="$(HOSTCFLAGS)" \
                HOSTCXX="$(HOSTCXX)" \
                INSTALL_HDR_PATH=$(LINUX_HEADERS_DIR) \
                headers_install \
        )

Re: LZMA inclusion

[Sam Ravnborg]

> 
> PS: Not sure if you, Sam, are the right person who cares for it, but
> i think that the help-text and actual accepted arguments of
> scripts/kconfig/lxdialog/check-lxdialog.sh are out of sync.
I queued up the following:
From f6682f915760ccfe57ef1b6cd5ff2d8f2bf8c1d4 Mon Sep 17 00:00:00 2001
From: Sam Ravnborg <sam@ravnborg.org>
Date: Wed, 3 Dec 2008 22:11:14 +0100
Subject: [PATCH] kconfig: fix options to check-lxdialog.sh

As noted by Bernhard - fix it up.

Cc: Bernhard Reutner-Fischer <rep.dot.nop@gmail.com>
Signed-off-by: Sam Ravnborg <sam@ravnborg.org>
---
 scripts/kconfig/lxdialog/check-lxdialog.sh |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/scripts/kconfig/lxdialog/check-lxdialog.sh b/scripts/kconfig/lxdialog/check-lxdialog.sh
index 5552154..fcef0f5 100644
--- a/scripts/kconfig/lxdialog/check-lxdialog.sh
+++ b/scripts/kconfig/lxdialog/check-lxdialog.sh
@@ -52,7 +52,7 @@ EOF
 }

 usage() {
-       printf "Usage: $0 [-check compiler options|-header|-library]\n"
+       printf "Usage: $0 [-check compiler options|-ccflags|-ldflags compiler options]\n"
 }

 if [ $# -eq 0 ]; then




> PPS: I did not verify if this is still the case, but I have this
> comment as a reminder for a small issue with "archprepare" versus
> headers_install, fwiw. It would be very handy if i could fuse those
> two into a simple "make ... archprepare headers_install":

Which architectures needs this archprepare?
It would be good to get rid of the dependency.

PS. I consider archprepare an internal target.
If some preparation is needed the recommended target is 'prepare'.
The day no targets has any special things they need to do archprepare will die.

	Sam

Re: LZMA inclusion

[Bernhard Reutner-Fischer]

On Wed, Dec 03, 2008 at 10:16:17PM +0100, Sam Ravnborg wrote:
>> 
>> PS: Not sure if you, Sam, are the right person who cares for it, but
>> i think that the help-text and actual accepted arguments of
>> scripts/kconfig/lxdialog/check-lxdialog.sh are out of sync.
>I queued up the following:

Thanks alot.
>
>> PPS: I did not verify if this is still the case, but I have this
>> comment as a reminder for a small issue with "archprepare" versus
>> headers_install, fwiw. It would be very handy if i could fuse those
>> two into a simple "make ... archprepare headers_install":
>
>Which architectures needs this archprepare?

At least cris tripped this IIRC, at least before or around the time
when cris's subarch handling was fixed (the asm-cris/arch-v10 vs.
arch-v32 linking issue).

>It would be good to get rid of the dependency.

nod

>PS. I consider archprepare an internal target.
>If some preparation is needed the recommended target is 'prepare'.
>The day no targets has any special things they need to do archprepare will die.

The proper solution would perhaps be to do have prepare or archprepare
as a prerequisite of headers_install as long as those are needed, i guess.

I as a user don't want to be bothered with this mere implementation detail
in the first place, yes.

Re: LZMA inclusion

[Sam Ravnborg]

> >> two into a simple "make ... archprepare headers_install":
> >
> >Which architectures needs this archprepare?
> 
> At least cris tripped this IIRC, at least before or around the time
> when cris's subarch handling was fixed (the asm-cris/arch-v10 vs.
> arch-v32 linking issue).

>>It would be good to get rid of the dependency.
> 
> nod
> 
> >PS. I consider archprepare an internal target.
> >If some preparation is needed the recommended target is 'prepare'.
> >The day no targets has any special things they need to do archprepare will die.
> 
> The proper solution would perhaps be to do have prepare or archprepare
> as a prerequisite of headers_install as long as those are needed, i guess.

We need to run as little arch specific stuff as possible for
headers_install so adding this prerequisite would just hide the real
issue that the arch has some latent bug to be fixed.
For cris we fixed it when we moved the headers (Jesper did - I was not involved).

So if you could check it out and see if other archs need it I would be glad.
If there are others I will try to get these fixed so they do not need archprepare
for headers_isntall.

	Sam

Re: LZMA inclusion

[Lasse Collin]

Bernhard Reutner-Fischer wrote:
> On Wed, Dec 03, 2008 at 11:36:45AM -0800, Tim Bird wrote:
> >Gregers Petersen wrote:
> >> There was a small talk a few days ago involving a few of the
> >> OpenWrt developers and David Woodhouse. One of the topics
> >> discussed, was a question about the potential of including LZMA in
> >> the kernel. Such an inclusion would be quite benefitial in terms
> >> of embedded systems, but the major hurdle seems to be the code
> >> quality of LZMA itself. This leads to the question I would like to
> >> raise; are there ongoing plans (or considerations) to rewrite and
> >> merge LZMA, and has anyone started working on it in practical
> >> terms?
> >
> >Did anyone answer this?  CELF is currently considering funding
> >a project to do this (add LZMA support to the kernel), and
> >it would be good to get a feel for the current status...
> > -- Tim
>
> AFAIK xz will be/is incompatible with this older LZMA, perhaps
> larhzu wants to chime in on that.

There's the LZMA algorithm, which is used at least in the .7z and .lzma 
file formats. There are two command line tools called lzma with 
different command line syntax: the one shipped in LZMA SDK (7-zip.org) 
and the gzip-like lzma tool from LZMA Utils (tukaani.org). Both of 
these lzma tools use the same .lzma format, which has only a very 
primitive header prefixed to the actual raw LZMA data (no magic bytes 
and no integrity check like CRC32).

The .lzma format will be deprecated once the new .xz format and related 
tools are available. The .xz format will be supported by 7-Zip and LZMA 
Utils; LZMA Utils will probably be renamed to plain "xz". The xz 
package will include a zlib-like compression library called liblzma, 
and gzip-like command line tool named xz. While .lzma and .xz are 
incompatible file formats, the xz package will also support the 
old .lzma format to ease transition to the .xz format.

The primary compression algorithm of the .xz format is LZMA2. It fixes 
some practical problems of the original LZMA. The .xz format also 
supports filters for executable data (x86, ARM and a few others), which 
combined with LZMA2 usually improve compression ratio 5-10 % over plain 
LZMA or LZMA2. I suppose such filters would be useful in the kernel, 
since the kernel image and iniramfs contain mostly executable code.

Final version of the .xz format specification will be released in this 
month. I try to get the first stable release or at least a good beta 
release of the xz package out in this month too.

Once the stable release of the xz package is out, I could be willing to 
write an easy-to-use .xz decoder that is suitable for inclusion to 
Linux (including proper coding style with comments). I have understood, 
that for kernel and initramfs compression as well as for SquashFS, it 
would be enough to support single-call buffer-to-buffer decoding 
(comparable to uncompress() in zlib). Such code can be significantly 
simpler than stateful multi-call implementation.

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

Re: LZMA inclusion

[Jean-Christophe PLAGNIOL-VILLARD]

> The primary compression algorithm of the .xz format is LZMA2. It fixes 
> some practical problems of the original LZMA. The .xz format also 
> supports filters for executable data (x86, ARM and a few others), which 
> combined with LZMA2 usually improve compression ratio 5-10 % over plain 
> LZMA or LZMA2. I suppose such filters would be useful in the kernel, 
> since the kernel image and iniramfs contain mostly executable code.
> 
> Final version of the .xz format specification will be released in this 
> month. I try to get the first stable release or at least a good beta 
> release of the xz package out in this month too.
> 
> Once the stable release of the xz package is out, I could be willing to 
> write an easy-to-use .xz decoder that is suitable for inclusion to 
> Linux (including proper coding style with comments). I have understood, 
> that for kernel and initramfs compression as well as for SquashFS, it 
> would be enough to support single-call buffer-to-buffer decoding 
> (comparable to uncompress() in zlib). Such code can be significantly 
> simpler than stateful multi-call implementation.

This sound very good.
Please note that we also use it in U-Boot so if could help us to have it also
in it. It will be usefull

Best Regards,
J.

Re: LZMA inclusion

[Geert Uytterhoeven]

On Wed, 3 Dec 2008, Lasse Collin wrote:
> Once the stable release of the xz package is out, I could be willing to 
> write an easy-to-use .xz decoder that is suitable for inclusion to 
> Linux (including proper coding style with comments). I have understood, 
> that for kernel and initramfs compression as well as for SquashFS, it 
> would be enough to support single-call buffer-to-buffer decoding 
> (comparable to uncompress() in zlib). Such code can be significantly 
> simpler than stateful multi-call implementation.

SquashFS does not do one-shot decompression, it calls the decompressor multiple
times, after reading each block. I guess that can be changed, but it will
increase memory pressure, as blocks cannot be released until the decompression
has finished.

Other compressed file systems that use (de)compression through the crypto API
do use one-shot (de)compression, as the current crypto API doesn't support
partial (de)compression. That includes Ubifs. Note that I'm working on
enhancing the crypto API to relax this limitation.

So please provide a stateful multi-call implementation ;-)

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010

Re: LZMA inclusion

[Lasse Collin]

Geert Uytterhoeven wrote:
> SquashFS does not do one-shot decompression, it calls the
> decompressor multiple times, after reading each block. I guess that
> can be changed, but it will increase memory pressure, as blocks
> cannot be released until the decompression has finished.

I read the code more carefully now. SquashFS does use multi-call 
decoding, but SquashFS-LZMA has been modified to use single-call 
decoding. It copies the input first to a 1 MiB buffer, and then decodes 
it with a single function call. I can understand if this isn't desired.

> Other compressed file systems that use (de)compression through the
> crypto API do use one-shot (de)compression, as the current crypto API
> doesn't support partial (de)compression. That includes Ubifs. Note
> that I'm working on enhancing the crypto API to relax this
> limitation.
>
> So please provide a stateful multi-call implementation ;-)

OK, I can do that once I have a stable release of the xz package out. 
Multi-call decoder will be a little bit bigger than a single-call 
version, but probably it's not too bad in practice.

Keeping the memory usage of the multi-call decoder reasonably low may be 
worth some extra effort. This needs some very basic understanding of 
the algorithms in use. Sorry if the next paragraphs don't contain any 
new information to you; I just thought that it is good to explain it 
just in case.

Both Deflate (zlib) and LZMA are LZ77-based algorithms. The decoder has 
a history buffer (i.e. dictionary), that holds the most recently 
decoded data. With single-call decoding, the output buffer can be used 
as the history buffer. Thus, even if the data was encoded using a big 
dictionary for better compression ratio, it doesn't increase the memory 
requirements of the decoder.

In a multi-call implementation, the history buffer is needed as part of 
the decoder state. The decoder first decodes the data into the history 
buffer, and then uses memcpy to copy the new data to the actual output 
buffer. With Deflate, the history buffer is almost always 32 KiB. Thus, 
the most recently decoded 32 KiB of data is always kept in memory as 
part of the multi-call decoder state.

With LZMA, 8 MiB is a typical size for the dictionary in user space 
applications. With SquashFS, the maximum reasonable dictionary size is 
1 MiB because that's the maximum size of the SquashFS block. (Making 
the dictionary bigger than the data being compressed doesn't improve 
the compression ratio.)

While LZMA compresses better than Deflate even with small dictionaries, 
I suppose that people will want to use big dictionary with LZMA and 
SquashFS. For example, with patches from squashfs-lzma.org, mksquashfs 
by default sets the LZMA dictionary size to the same value as the 
SquashFS block size, because this gives the best compression ratio.

I suppose that it is not nice to need 1 MiB (maximum SquashFS block 
size) of extra memory as part of multi-call decoder state. This can be 
avoided if the code using the multi-call decoder keeps the whole output 
buffer available and doesn't look at its contents until the decoding 
has been successfully finished. This way even the multi-call decoder 
can use the output buffer as a history buffer.

To my understanding, this trick would be OK in SquashFS (with or without 
the patches from squashfs-lzma.org), since SquashFS doesn't touch the 
output buffer until decoding has been finished. So by using multi-call 
decoding, it is possible to avoid needing the whole compressed input in 
memory at once, and by keeping the whole output buffer available until 
the end of the decoding, it is possible to keep the multi-call 
decoder's state more reasonable (below 100 KiB).

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. It is important that this 
flag requires that the caller doesn't touch the partial output buffer 
_at all_. This is because if some additional filter is combined with 
LZMA2 in a .xz file, the output buffer won't have any valid data until 
the decoding has been truly finished.

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

Re: LZMA inclusion

[Jörn Engel]

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.

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.

Jörn

-- 
It's not whether you win or lose, it's how you place the blame.
-- unknown

Re: LZMA inclusion

[Phillip Lougher]

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
> 

Re: LZMA inclusion

[Jamie Lokier]

Phillip Lougher wrote:
> 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.

If the kernel has trouble even vmallocing 1MiB, the LZMA algorithm
will need reworking to explicitly use discontiguous workspace buffers
anyway, regardless of whether the output buffer is used as workspace.

If the kernel can vmalloc 1MiB easily, then in principle it could map
the discontiguous output buffer temporarily into a contiguous region
of vmalloc address space, avoiding the allocation.

Instead of memcpy, you'd have some cache coherency fun on some
architectures.

-- Jamie

Re: LZMA inclusion

[Lasse Collin]

Phillip Lougher wrote:
> 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).

To my understanding, using 4 KiB output buffers can make sense only if 
the dictionary size is significantly smaller than the Squashfs block 
size. This is because an output buffer scattered to 4 KiB pieces means 
that the the dictionary has to be vmalloced as part of the LZMA decoder 
state.

For example, if the dictionary size is equal to the Squashfs block size, 
the same amount of memory that earlier Squashfs versions vmalloced for 
the output buffer is now vmalloced by the uncompression code for the 
dictionary. Plus, memcpy is needed to get the data from the dictionary 
to the 4 KiB output buffers.

LZMA decoder accesses the dictionary contents quite randomly, copying 
1-273 bytes at a time from some unpredictable offset to the end of the 
dictionary. The offsets are relative to the end of the dictionary (i.e. 
the current write position). I suppose the dictionary buffer has to be 
contiguous in the virtual address space. Otherwise the decoder needs to 
emulate it to find the offsets in the dictionary. That would probably 
make things very slow.

Naturally it might be OK to decrease the maximum dictionary size allowed 
in multi-call decoder. I'm not sure if going from 1 MiB to e.g. 128 KiB 
dictionary while keeping the 1 MiB Squashfs block size affects 
compression ratio too much. I guess it means 2-8 % bigger result, but 
someone should test it with real-world file system data. 

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

Re: LZMA inclusion

[Phillip Lougher]

Lasse Collin wrote:
> Phillip Lougher wrote:
>> 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).
> 
> To my understanding, using 4 KiB output buffers can make sense only if 
> the dictionary size is significantly smaller than the Squashfs block 
> size. This is because an output buffer scattered to 4 KiB pieces means 
> that the the dictionary has to be vmalloced as part of the LZMA decoder 
> state.
> 
> For example, if the dictionary size is equal to the Squashfs block size, 
> the same amount of memory that earlier Squashfs versions vmalloced for 
> the output buffer is now vmalloced by the uncompression code for the 
> dictionary. Plus, memcpy is needed to get the data from the dictionary 
> to the 4 KiB output buffers.
> 

The issue that moving to 4 KiB output buffers solves is it reduces 
significantly the number of 1 MiB (or 128 KiB for the default block 
size) buffers that need to be vmalloced.  Squashfs caches the last 3 
fragment buffers read, and moving to 4 KiB buffers eliminates these 
vmallocs.

Obviously moving to 4 KiB output buffers will require a 1 MiB dictionary 
workspace to be vmalloced, but this is still much less than the 3 
buffers that currently need to be vmalloced.

Phillip

Re: LZMA inclusion

[Jörn Engel]

On Sun, 7 December 2008 23:32:32 +0000, Phillip Lougher wrote:
> 
> 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.

Don't blame lkml, blame Intel and IBM.  Back in the days of the 386, a
beefy machine had 8MB of physical memory and 4GB of virtual memory
space.  Noone had to worry about fragmentation anymore.  If you needed a
1MB buffer, you'd just round up some 256 pages and instruct the mmu to
map them into a large contiguous address range in the virtual address
space.  Life was good indeed.

But physical memory has constantly grown since, while the virtual memory
space has for a long time stagnated.  Intel even introduced some
hardware hacks to use up to 64GB of physical memory with a measly 4GB of
virtual memory.  Now it was _virtual_ memory fragmentation that you had
to worry about.

These days most CPUs you'd buy are 64bit, so virtual memory space has
become useful again.  But as a kernel hacker, you have little control
over what hardware everyone is using.  And those weird systems with
more physical than virtual memory are still around. :(

Jörn

-- 
Don't patch bad code, rewrite it.
-- Kernigham and Pike, according to Rusty

Re: LZMA inclusion

[Phillip Lougher]

Jörn Engel wrote:
> On Sun, 7 December 2008 23:32:32 +0000, Phillip Lougher wrote:
>> 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.
> 
> Don't blame lkml, blame Intel and IBM.  Back in the days of the 386, a
> beefy machine had 8MB of physical memory and 4GB of virtual memory
> space.  Noone had to worry about fragmentation anymore.  If you needed a
> 1MB buffer, you'd just round up some 256 pages and instruct the mmu to
> map them into a large contiguous address range in the virtual address
> space.  Life was good indeed.
> 
> But physical memory has constantly grown since, while the virtual memory
> space has for a long time stagnated.  Intel even introduced some
> hardware hacks to use up to 64GB of physical memory with a measly 4GB of
> virtual memory.  Now it was _virtual_ memory fragmentation that you had
> to worry about.
> 
> These days most CPUs you'd buy are 64bit, so virtual memory space has
> become useful again.  But as a kernel hacker, you have little control
> over what hardware everyone is using.  And those weird systems with
> more physical than virtual memory are still around. :(
> 
> Jörn
> 

Yes, I'm aware of the issues with vmalloc on older hardware.

Re: LZMA inclusion

[Jörn Engel]

On Mon, 8 December 2008 21:47:37 +0000, Phillip Lougher wrote:
> 
> Yes, I'm aware of the issues with vmalloc on older hardware.

It's not even limited to older hardware.  Blue Gene supercomputers are
large clusters of ppc440 machines.  Iirc each node consists of two 32bit
cpus and up to 4GB of RAM.  Not likely to run squashfs, but hardly old
hardware either.

Or for a living room example, take a barebone with a VIA C7.  And maybe
fairly soon a large number of mobile phones will have close to 4GB RAM,
yet still run on 32bit ARM processors.  I fear those troubles are far
from gone.

Jörn

-- 
All art is but imitation of nature.
-- Lucius Annaeus Seneca

Re: LZMA inclusion

[Lasse Collin]

Phillip Lougher wrote:
> The issue that moving to 4 KiB output buffers solves is it reduces
> significantly the number of 1 MiB (or 128 KiB for the default block
> size) buffers that need to be vmalloced.  Squashfs caches the last 3
> fragment buffers read, and moving to 4 KiB buffers eliminates these
> vmallocs.
>
> Obviously moving to 4 KiB output buffers will require a 1 MiB
> dictionary workspace to be vmalloced, but this is still much less
> than the 3 buffers that currently need to be vmalloced.

Thanks for explaining.

Is it OK that the decoder allocates memory in the middle of decoding, or 
must all the memory be preallocated when the decoder is initialized? If 
everything has to be preallocated, then the initialization function 
needs an argument to specify how big dictionary must be supported. It 
doesn't make sense to allocate 1 MiB just in case if the caller knows 
that 128 KiB dictionary is the maximum that will ever be needed.

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

Re: LZMA inclusion

[Geert Uytterhoeven]

On Tue, 9 Dec 2008, Lasse Collin wrote:
> Phillip Lougher wrote:
> > The issue that moving to 4 KiB output buffers solves is it reduces
> > significantly the number of 1 MiB (or 128 KiB for the default block
> > size) buffers that need to be vmalloced.  Squashfs caches the last 3
> > fragment buffers read, and moving to 4 KiB buffers eliminates these
> > vmallocs.
> >
> > Obviously moving to 4 KiB output buffers will require a 1 MiB
> > dictionary workspace to be vmalloced, but this is still much less
> > than the 3 buffers that currently need to be vmalloced.
> 
> Thanks for explaining.
> 
> Is it OK that the decoder allocates memory in the middle of decoding, or 
> must all the memory be preallocated when the decoder is initialized? If 
> everything has to be preallocated, then the initialization function 
> needs an argument to specify how big dictionary must be supported. It 
> doesn't make sense to allocate 1 MiB just in case if the caller knows 
> that 128 KiB dictionary is the maximum that will ever be needed.

If you want to make it available through the crypto API, you cannot allocate
memory in the (de)compression routines theirselves, only in the initialization
function.

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010

Re: LZMA inclusion

[Lasse Collin]

Geert Uytterhoeven wrote:
> On Tue, 9 Dec 2008, Lasse Collin wrote:
> > Is it OK that the decoder allocates memory in the middle of
> > decoding, or must all the memory be preallocated when the decoder
> > is initialized? If everything has to be preallocated, then the
> > initialization function needs an argument to specify how big
> > dictionary must be supported. It doesn't make sense to allocate 1
> > MiB just in case if the caller knows that 128 KiB dictionary is the
> > maximum that will ever be needed.
>
> If you want to make it available through the crypto API, you cannot
> allocate memory in the (de)compression routines theirselves, only in
> the initialization function.

OK, thanks.

My work on the upcoming xz package has been progressing quite OK in the 
past two weeks. I suppose that I could start working on the kernel .xz 
decoder at some point in January 2009. I will post to linux-embedded 
once I have some working code to show (hopefully in February).

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