Adding LZ4 compression support to Btrfs

Adding LZ4 compression support to Btrfs

[Amy Parker]

The compression options in Btrfs are great, and help save a ton of
space on disk. Zstandard works extremely well for this, and is fairly
fast. However, it can heavily reduce the speed of quick disks, does
not work well on lower-end systems, and does not scale well across
multiple cores. Zlib is even slower and worse on compression ratio,
and LZO suffers on both the compression ratio and speed.

I've been laying out my plans for a backup software recently, and
stumbled upon LZ4. Tends to hover around LZO compression ratios.
Performs better than Zstandard and LZO slightly for compression - but
significantly outpaces them on decompression, which matters
significantly more for users:

zstd 1.4.5:
 - ratio 2.884
 - compression 500 MiB/s
 - decompression 1.66 GiB/s
zlib 1.2.11:
 - ratio 2.743
 - compression 90 MiB/s
 - decompression 400 MiB/s
lzo 2.10:
 - ratio 2.106
 - compression 690 MiB/s
 - decompression 820 MiB/s
lz4 1.9.2:
 - ratio 2.101
 - compression 740 MiB/s
 - decompression 4.5 GiB/s

LZ4's speeds are high enough to allow many applications which
previously declined to use any compression due to speed to increase
their possible space while keeping fast write and especially read
access.

What're thoughts like on adding something like LZ4 as a compression
option in btrfs? Is it feasible given the current implementation of
compression in btrfs?

   -Amy IP

Re: Adding LZ4 compression support to Btrfs

[Neal Gompa]

On Wed, Feb 24, 2021 at 11:10 PM Amy Parker <enbyamy@gmail.com> wrote:
>
> The compression options in Btrfs are great, and help save a ton of
> space on disk. Zstandard works extremely well for this, and is fairly
> fast. However, it can heavily reduce the speed of quick disks, does
> not work well on lower-end systems, and does not scale well across
> multiple cores. Zlib is even slower and worse on compression ratio,
> and LZO suffers on both the compression ratio and speed.
>
> I've been laying out my plans for a backup software recently, and
> stumbled upon LZ4. Tends to hover around LZO compression ratios.
> Performs better than Zstandard and LZO slightly for compression - but
> significantly outpaces them on decompression, which matters
> significantly more for users:
>
> zstd 1.4.5:
>  - ratio 2.884
>  - compression 500 MiB/s
>  - decompression 1.66 GiB/s
> zlib 1.2.11:
>  - ratio 2.743
>  - compression 90 MiB/s
>  - decompression 400 MiB/s
> lzo 2.10:
>  - ratio 2.106
>  - compression 690 MiB/s
>  - decompression 820 MiB/s
> lz4 1.9.2:
>  - ratio 2.101
>  - compression 740 MiB/s
>  - decompression 4.5 GiB/s
>
> LZ4's speeds are high enough to allow many applications which
> previously declined to use any compression due to speed to increase
> their possible space while keeping fast write and especially read
> access.
>
> What're thoughts like on adding something like LZ4 as a compression
> option in btrfs? Is it feasible given the current implementation of
> compression in btrfs?

This is definitely possible. I think the only reason lz4 isn't enabled
for Btrfs has been the lack of interest in it. I'd defer to some of
the kernel folks (I'm just a user and integrator myself), but I think
that's definitely worth having lz4 compression supported.



-- 
真実はいつも一つ！/ Always, there's only one truth!

Re: Adding LZ4 compression support to Btrfs

[David Sterba]

On Thu, Feb 25, 2021 at 08:18:53AM -0500, Neal Gompa wrote:
> On Wed, Feb 24, 2021 at 11:10 PM Amy Parker <enbyamy@gmail.com> wrote:
> >
> > The compression options in Btrfs are great, and help save a ton of
> > space on disk. Zstandard works extremely well for this, and is fairly
> > fast. However, it can heavily reduce the speed of quick disks, does
> > not work well on lower-end systems, and does not scale well across
> > multiple cores. Zlib is even slower and worse on compression ratio,
> > and LZO suffers on both the compression ratio and speed.
> >
> > I've been laying out my plans for a backup software recently, and
> > stumbled upon LZ4. Tends to hover around LZO compression ratios.
> > Performs better than Zstandard and LZO slightly for compression - but
> > significantly outpaces them on decompression, which matters
> > significantly more for users:
> >
> > zstd 1.4.5:
> >  - ratio 2.884
> >  - compression 500 MiB/s
> >  - decompression 1.66 GiB/s
> > zlib 1.2.11:
> >  - ratio 2.743
> >  - compression 90 MiB/s
> >  - decompression 400 MiB/s
> > lzo 2.10:
> >  - ratio 2.106
> >  - compression 690 MiB/s
> >  - decompression 820 MiB/s
> > lz4 1.9.2:
> >  - ratio 2.101
> >  - compression 740 MiB/s
> >  - decompression 4.5 GiB/s
> >
> > LZ4's speeds are high enough to allow many applications which
> > previously declined to use any compression due to speed to increase
> > their possible space while keeping fast write and especially read
> > access.
> >
> > What're thoughts like on adding something like LZ4 as a compression
> > option in btrfs? Is it feasible given the current implementation of
> > compression in btrfs?
> 
> This is definitely possible. I think the only reason lz4 isn't enabled
> for Btrfs has been the lack of interest in it. I'd defer to some of
> the kernel folks (I'm just a user and integrator myself), but I think
> that's definitely worth having lz4 compression supported.

LZ4 support has been asked for so many times that it has it's own FAQ
entry:
https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F

The decompression speed is not the only thing that should be evaluated,
the way compression works in btrfs (in 4k blocks) does not allow good
compression ratios and overall LZ4 does not do much better than LZO. So
this is not worth the additional costs of compatibility. With ZSTD we
got the high compression and recently there have been added real-time
compression levels that we'll use in btrfs eventually.

Re: Adding LZ4 compression support to Btrfs

[Filipe Manana]

On Thu, Feb 25, 2021 at 1:23 PM Neal Gompa <ngompa13@gmail.com> wrote:
>
> On Wed, Feb 24, 2021 at 11:10 PM Amy Parker <enbyamy@gmail.com> wrote:
> >
> > The compression options in Btrfs are great, and help save a ton of
> > space on disk. Zstandard works extremely well for this, and is fairly
> > fast. However, it can heavily reduce the speed of quick disks, does
> > not work well on lower-end systems, and does not scale well across
> > multiple cores. Zlib is even slower and worse on compression ratio,
> > and LZO suffers on both the compression ratio and speed.
> >
> > I've been laying out my plans for a backup software recently, and
> > stumbled upon LZ4. Tends to hover around LZO compression ratios.
> > Performs better than Zstandard and LZO slightly for compression - but
> > significantly outpaces them on decompression, which matters
> > significantly more for users:
> >
> > zstd 1.4.5:
> >  - ratio 2.884
> >  - compression 500 MiB/s
> >  - decompression 1.66 GiB/s
> > zlib 1.2.11:
> >  - ratio 2.743
> >  - compression 90 MiB/s
> >  - decompression 400 MiB/s
> > lzo 2.10:
> >  - ratio 2.106
> >  - compression 690 MiB/s
> >  - decompression 820 MiB/s
> > lz4 1.9.2:
> >  - ratio 2.101
> >  - compression 740 MiB/s
> >  - decompression 4.5 GiB/s
> >
> > LZ4's speeds are high enough to allow many applications which
> > previously declined to use any compression due to speed to increase
> > their possible space while keeping fast write and especially read
> > access.
> >
> > What're thoughts like on adding something like LZ4 as a compression
> > option in btrfs? Is it feasible given the current implementation of
> > compression in btrfs?
>
> This is definitely possible. I think the only reason lz4 isn't enabled
> for Btrfs has been the lack of interest in it. I'd defer to some of
> the kernel folks (I'm just a user and integrator myself), but I think
> that's definitely worth having lz4 compression supported.

This has been brought up over and over for many years:

https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F

Things have to be evaluated in btrfs' context, i.e. how it uses compression.
More details there anyway.

>
>
>
> --
> 真実はいつも一つ！/ Always, there's only one truth!



-- 
Filipe David Manana,

“Whether you think you can, or you think you can't — you're right.”

Re: Adding LZ4 compression support to Btrfs

[Eric Biggers]

On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> 
> LZ4 support has been asked for so many times that it has it's own FAQ
> entry:
> https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> 
> The decompression speed is not the only thing that should be evaluated,
> the way compression works in btrfs (in 4k blocks) does not allow good
> compression ratios and overall LZ4 does not do much better than LZO. So
> this is not worth the additional costs of compatibility. With ZSTD we
> got the high compression and recently there have been added real-time
> compression levels that we'll use in btrfs eventually.

When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
up to 128KB at a time
(https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
So which is it -- 4KB or 128KB?

- Eric

Re: Adding LZ4 compression support to Btrfs

[Amy Parker]

Thanks for your comments, Jim. I was originally going to abandon my
thoughts about LZ4 on btrfs - but I didn't realize that FAQ was from
2014.

> lz4 has had ongoing development and now exists in other linux kernel fs's.
What other filesystems currently employ LZ4? Not as familiar with it
being used on other filesystems.

   -Amy IP

Re: Adding LZ4 compression support to Btrfs

[Neal Gompa]

On Thu, Feb 25, 2021 at 6:18 PM Amy Parker <enbyamy@gmail.com> wrote:
>
> Thanks for your comments, Jim. I was originally going to abandon my
> thoughts about LZ4 on btrfs - but I didn't realize that FAQ was from
> 2014.
>
> > lz4 has had ongoing development and now exists in other linux kernel fs's.
> What other filesystems currently employ LZ4? Not as familiar with it
> being used on other filesystems.
>

In the Linux kernel, both SquashFS and F2FS have LZ4 compression support.



-- 
真実はいつも一つ！/ Always, there's only one truth!

Re: Adding LZ4 compression support to Btrfs

[Gao Xiang]

On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> > 
> > LZ4 support has been asked for so many times that it has it's own FAQ
> > entry:
> > https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> > 
> > The decompression speed is not the only thing that should be evaluated,
> > the way compression works in btrfs (in 4k blocks) does not allow good
> > compression ratios and overall LZ4 does not do much better than LZO. So
> > this is not worth the additional costs of compatibility. With ZSTD we
> > got the high compression and recently there have been added real-time
> > compression levels that we'll use in btrfs eventually.
> 
> When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
> up to 128KB at a time
> (https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
> So which is it -- 4KB or 128KB?
> 

I think it was to say in one 4kb block there are no 2 different
compress extents, so there is no noticable extra space saving
difference if compression algorithms (e.g. LZ4 vs LZO) with very
similiar C/R. I think that conclusion is also be applied to F2FS
compression as I said months ago before.

LZ4 has better decompression speed (also has better decompression
speed / CR ratio) due to LZ4 block format design. Apart from
compatibility concern, IMO LZ4 is much better than LZO (Also LZ4
itself is much actively maintainence compared with LZO as well.)

Thanks,
Gao Xiang

> - Eric

Re: Adding LZ4 compression support to Btrfs

[David Sterba]

On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> > 
> > LZ4 support has been asked for so many times that it has it's own FAQ
> > entry:
> > https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> > 
> > The decompression speed is not the only thing that should be evaluated,
> > the way compression works in btrfs (in 4k blocks) does not allow good
> > compression ratios and overall LZ4 does not do much better than LZO. So
> > this is not worth the additional costs of compatibility. With ZSTD we
> > got the high compression and recently there have been added real-time
> > compression levels that we'll use in btrfs eventually.
> 
> When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
> up to 128KB at a time
> (https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
> So which is it -- 4KB or 128KB?

Logical extent ranges are sliced to 128K that are submitted to the
compression routine. Then, the whole range is fed by 4K (or more exactly
by page sized chunks) to the compression. Depending on the capabilities
of the compression algorithm, the 4K chunks are either independent or
can reuse some internal state of the algorithm.

LZO and LZ4 use some kind of embedded dictionary in the same buffer, and
references to that dictionary directly. Ie. assuming the whole input
range to be contiguous. Which is something that's not trivial to achive
in kernel because of pages that are not contiguous in general.

Thus, LZO and LZ4 compress 4K at a time, each chunk is independent. This
results in worse compression ratio because of less data reuse
possibilities. OTOH this allows decompression in place.

ZLIB and ZSTD can have a separate dictionary and don't need the input
chunks to be contiguous. This brings some additional overhead like
copying parts of the input to the dictionary and additional memory for
themporary structures, but with higher compression ratios.

IIRC the biggest problem for LZ4 was the cost of setting up each 4K
chunk, the work memory had to be zeroed. The size of the work memory is
tunable but trading off compression ratio. Either way it was either too
slow or too bad.

Re: Adding LZ4 compression support to Btrfs

[Gao Xiang]

On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> > > 
> > > LZ4 support has been asked for so many times that it has it's own FAQ
> > > entry:
> > > https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> > > 
> > > The decompression speed is not the only thing that should be evaluated,
> > > the way compression works in btrfs (in 4k blocks) does not allow good
> > > compression ratios and overall LZ4 does not do much better than LZO. So
> > > this is not worth the additional costs of compatibility. With ZSTD we
> > > got the high compression and recently there have been added real-time
> > > compression levels that we'll use in btrfs eventually.
> > 
> > When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
> > up to 128KB at a time
> > (https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
> > So which is it -- 4KB or 128KB?
> 
> Logical extent ranges are sliced to 128K that are submitted to the
> compression routine. Then, the whole range is fed by 4K (or more exactly
> by page sized chunks) to the compression. Depending on the capabilities
> of the compression algorithm, the 4K chunks are either independent or
> can reuse some internal state of the algorithm.
> 
> LZO and LZ4 use some kind of embedded dictionary in the same buffer, and
> references to that dictionary directly. Ie. assuming the whole input
> range to be contiguous. Which is something that's not trivial to achive
> in kernel because of pages that are not contiguous in general.
> 
> Thus, LZO and LZ4 compress 4K at a time, each chunk is independent. This
> results in worse compression ratio because of less data reuse
> possibilities. OTOH this allows decompression in place.

Sorry about the noise before. I misread btrfs LZO implementation.
Yet it sounds that approach has lower CR than compress 128kb as
a while. In principle it can archive decompress in-place (margin
by a whole lzo chunk), yet LZ4/LZO algorithm can have a more
accurate lower inplace margin in math.

> 
> ZLIB and ZSTD can have a separate dictionary and don't need the input
> chunks to be contiguous. This brings some additional overhead like
> copying parts of the input to the dictionary and additional memory for
> themporary structures, but with higher compression ratios.
> 
> IIRC the biggest problem for LZ4 was the cost of setting up each 4K
> chunk, the work memory had to be zeroed. The size of the work memory is
> tunable but trading off compression ratio. Either way it was either too
> slow or too bad.

May I ask why LZ4 needs to zero the work memory (if you mean dest
buffer and LZ4_decompress_safe), just out of curiousity... I didn't
see that restriction before. Thanks!

Thanks,
Gao Xiang

Re: Adding LZ4 compression support to Btrfs

[Gao Xiang]

On Fri, Feb 26, 2021 at 07:28:54PM +0800, Gao Xiang wrote:
> On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> > On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > > On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> > > > 
> > > > LZ4 support has been asked for so many times that it has it's own FAQ
> > > > entry:
> > > > https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> > > > 
> > > > The decompression speed is not the only thing that should be evaluated,
> > > > the way compression works in btrfs (in 4k blocks) does not allow good
> > > > compression ratios and overall LZ4 does not do much better than LZO. So
> > > > this is not worth the additional costs of compatibility. With ZSTD we
> > > > got the high compression and recently there have been added real-time
> > > > compression levels that we'll use in btrfs eventually.
> > > 
> > > When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
> > > up to 128KB at a time
> > > (https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
> > > So which is it -- 4KB or 128KB?
> > 
> > Logical extent ranges are sliced to 128K that are submitted to the
> > compression routine. Then, the whole range is fed by 4K (or more exactly
> > by page sized chunks) to the compression. Depending on the capabilities
> > of the compression algorithm, the 4K chunks are either independent or
> > can reuse some internal state of the algorithm.
> > 
> > LZO and LZ4 use some kind of embedded dictionary in the same buffer, and
> > references to that dictionary directly. Ie. assuming the whole input
> > range to be contiguous. Which is something that's not trivial to achive
> > in kernel because of pages that are not contiguous in general.
> > 
> > Thus, LZO and LZ4 compress 4K at a time, each chunk is independent. This
> > results in worse compression ratio because of less data reuse
> > possibilities. OTOH this allows decompression in place.
> 
> Sorry about the noise before. I misread btrfs LZO implementation.
> Yet it sounds that approach has lower CR than compress 128kb as
> a while. In principle it can archive decompress in-place (margin
> by a whole lzo chunk), yet LZ4/LZO algorithm can have a more
> accurate lower inplace margin in math.
> 
> > 
> > ZLIB and ZSTD can have a separate dictionary and don't need the input
> > chunks to be contiguous. This brings some additional overhead like
> > copying parts of the input to the dictionary and additional memory for
> > themporary structures, but with higher compression ratios.
> > 
> > IIRC the biggest problem for LZ4 was the cost of setting up each 4K
> > chunk, the work memory had to be zeroed. The size of the work memory is
> > tunable but trading off compression ratio. Either way it was either too
> > slow or too bad.
> 
> May I ask why LZ4 needs to zero the work memory (if you mean dest
> buffer and LZ4_decompress_safe), just out of curiousity... I didn't
> see that restriction before. Thanks!

Oh, looking back again, there is a difference between kernel LZ4 code
[1] and lz4 upstream[2] that I didn't notice. If "work memory" above
is that and I understand correctly, no need to zero that memory except
something unique occurs to the kernel implementation itself (Also, it
seems that f2fs compression doesn't zero it when using at least [3],
although I never tried such LZ4 kernel-specific compress interface
before.)

[1] https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L1373
[2] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/lz4/lz4_compress.c#n511
[3] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/f2fs/compress.c#n262

Thanks,
Gao Xiang

> 
> Thanks,
> Gao Xiang
> 

Re: Adding LZ4 compression support to Btrfs

[David Sterba]

On Fri, Feb 26, 2021 at 07:28:54PM +0800, Gao Xiang wrote:
> On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> > On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > 
> > ZLIB and ZSTD can have a separate dictionary and don't need the input
> > chunks to be contiguous. This brings some additional overhead like
> > copying parts of the input to the dictionary and additional memory for
> > themporary structures, but with higher compression ratios.
> > 
> > IIRC the biggest problem for LZ4 was the cost of setting up each 4K
> > chunk, the work memory had to be zeroed. The size of the work memory is
> > tunable but trading off compression ratio. Either way it was either too
> > slow or too bad.
> 
> May I ask why LZ4 needs to zero the work memory (if you mean dest
> buffer and LZ4_decompress_safe), just out of curiousity... I didn't
> see that restriction before. Thanks!

Not the destination buffer, but the work memory or state as it can be
also called. This is from my initial interest in lz4 in 2012 and I got
that from Yann himself.  There was a tradeoff to either expect zeroed
work memory or add more conditionals.

At time he got some benchmark result and the conditionals came out
worse. And I see the memset is still there (see below) so there's been
no change.

For example in f2fs sources there is:
lz4_compress_pages
  LZ4_compress_default (cc->private is the work memory)
    LZ4_compress_fast
      LZ4_compress_fast_extState
        LZ4_resetStream
	  memset

Where the state size LZ4_MEM_COMPRESS is hidden in the maze od defines

#define LZ4_MEM_COMPRESS	LZ4_STREAMSIZE
#define LZ4_STREAMSIZE	(LZ4_STREAMSIZE_U64 * sizeof(unsigned long long))
#define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE - 3)) + 4)
/*
 * LZ4_MEMORY_USAGE :
 * Memory usage formula : N->2^N Bytes
 * (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
 * Increasing memory usage improves compression ratio
 * Reduced memory usage can improve speed, due to cache effect
 * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache
 */
#define LZ4_MEMORY_USAGE 14

So it's 16K by default in linux. Now imagine doing memset(16K) just to
compress 4K, and do that 32 times to compress the whole 128K chunk.
That's not a negligible overhead.

Re: Adding LZ4 compression support to Btrfs

[Gao Xiang]

Hi David,

On Fri, Feb 26, 2021 at 03:12:03PM +0100, David Sterba wrote:
> On Fri, Feb 26, 2021 at 07:28:54PM +0800, Gao Xiang wrote:
> > On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> > > On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > > 
> > > ZLIB and ZSTD can have a separate dictionary and don't need the input
> > > chunks to be contiguous. This brings some additional overhead like
> > > copying parts of the input to the dictionary and additional memory for
> > > themporary structures, but with higher compression ratios.
> > > 
> > > IIRC the biggest problem for LZ4 was the cost of setting up each 4K
> > > chunk, the work memory had to be zeroed. The size of the work memory is
> > > tunable but trading off compression ratio. Either way it was either too
> > > slow or too bad.
> > 
> > May I ask why LZ4 needs to zero the work memory (if you mean dest
> > buffer and LZ4_decompress_safe), just out of curiousity... I didn't
> > see that restriction before. Thanks!
> 
> Not the destination buffer, but the work memory or state as it can be
> also called. This is from my initial interest in lz4 in 2012 and I got
> that from Yann himself.  There was a tradeoff to either expect zeroed
> work memory or add more conditionals.
> 
> At time he got some benchmark result and the conditionals came out
> worse. And I see the memset is still there (see below) so there's been
> no change.
> 
> For example in f2fs sources there is:
> lz4_compress_pages
>   LZ4_compress_default (cc->private is the work memory)
>     LZ4_compress_fast
>       LZ4_compress_fast_extState
>         LZ4_resetStream
> 	  memset
> 
> Where the state size LZ4_MEM_COMPRESS is hidden in the maze od defines
> 
> #define LZ4_MEM_COMPRESS	LZ4_STREAMSIZE
> #define LZ4_STREAMSIZE	(LZ4_STREAMSIZE_U64 * sizeof(unsigned long long))
> #define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE - 3)) + 4)
> /*
>  * LZ4_MEMORY_USAGE :
>  * Memory usage formula : N->2^N Bytes
>  * (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
>  * Increasing memory usage improves compression ratio
>  * Reduced memory usage can improve speed, due to cache effect
>  * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache
>  */
> #define LZ4_MEMORY_USAGE 14
> 
> So it's 16K by default in linux. Now imagine doing memset(16K) just to
> compress 4K, and do that 32 times to compress the whole 128K chunk.
> That's not a negligible overhead.

Ok, thanks for your reply & info. I get the concern now. That is mainly a
internal HASHTABLE for LZ4 matchfinder (most LZ algs use hash table as a way
to find a previous match) to get len-distance pair from history sliding
window. I just did a quick glance, If I understand correctly, I think LZO
has a similiar table (yet not quite sure since I don't looked into that
much), see:

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/lzo/lzodefs.h#n68
#define D_BITS		13
#define D_SIZE		(1u << D_BITS)

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/lzo/lzo1x_compress.c#n108
t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK;
m_pos = in + dict[t];
dict[t] = (lzo_dict_t) (ip - in);
if (unlikely(dv != get_unaligned_le32(m_pos)))
	goto literal;

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/lzo/lzo1x_compress.c#n334
memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));

LZO uses 13 but LZ4 uses 14, so in principle less collision. But it can
be tunable especially considering btrfs 4kb fixed-sized input compression,
it seems double memset though (16kb vs 8kb)..

Thanks,
Gao Xiang

> 

Re: Adding LZ4 compression support to Btrfs

[Eric Biggers]

On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:
> > > 
> > > LZ4 support has been asked for so many times that it has it's own FAQ
> > > entry:
> > > https://btrfs.wiki.kernel.org/index.php/FAQ#Will_btrfs_support_LZ4.3F
> > > 
> > > The decompression speed is not the only thing that should be evaluated,
> > > the way compression works in btrfs (in 4k blocks) does not allow good
> > > compression ratios and overall LZ4 does not do much better than LZO. So
> > > this is not worth the additional costs of compatibility. With ZSTD we
> > > got the high compression and recently there have been added real-time
> > > compression levels that we'll use in btrfs eventually.
> > 
> > When ZSTD support was being added to btrfs, it was claimed that btrfs compresses
> > up to 128KB at a time
> > (https://lore.kernel.org/r/5a7c09dd-3415-0c00-c0f2-a605a0656499@fb.com).
> > So which is it -- 4KB or 128KB?
> 
> Logical extent ranges are sliced to 128K that are submitted to the
> compression routine. Then, the whole range is fed by 4K (or more exactly
> by page sized chunks) to the compression. Depending on the capabilities
> of the compression algorithm, the 4K chunks are either independent or
> can reuse some internal state of the algorithm.
> 
> LZO and LZ4 use some kind of embedded dictionary in the same buffer, and
> references to that dictionary directly. Ie. assuming the whole input
> range to be contiguous. Which is something that's not trivial to achive
> in kernel because of pages that are not contiguous in general.
> 
> Thus, LZO and LZ4 compress 4K at a time, each chunk is independent. This
> results in worse compression ratio because of less data reuse
> possibilities. OTOH this allows decompression in place.
> 
> ZLIB and ZSTD can have a separate dictionary and don't need the input
> chunks to be contiguous. This brings some additional overhead like
> copying parts of the input to the dictionary and additional memory for
> themporary structures, but with higher compression ratios.
> 
> IIRC the biggest problem for LZ4 was the cost of setting up each 4K
> chunk, the work memory had to be zeroed. The size of the work memory is
> tunable but trading off compression ratio. Either way it was either too
> slow or too bad.

Okay so you have 128K to compress, but not in a virtually contiguous buffer, so
you need the algorithm to support streaming of 4K chunks.  And the LZ4
implementation doesn't properly support that.  (Note that this is a property of
the LZ4 *implementation*, not the LZ4 *format*.)

How about using vm_map_ram() to get a contiguous buffer, like what f2fs does?
Then you wouldn't need streaming support.

There is some overhead in setting up page mappings, but it might actually turn
out to be faster (also for the other algorithms, not just LZ4) since it avoids
the overhead of streaming, such as the algorithm having to copy all the data
into an internal buffer for matchfinding.

- Eric

Re: Adding LZ4 compression support to Btrfs

[David Sterba]

On Fri, Feb 26, 2021 at 08:39:47AM -0800, Eric Biggers wrote:
> On Fri, Feb 26, 2021 at 10:36:53AM +0100, David Sterba wrote:
> > On Thu, Feb 25, 2021 at 10:50:56AM -0800, Eric Biggers wrote:
> > > On Thu, Feb 25, 2021 at 02:26:47PM +0100, David Sterba wrote:

> Okay so you have 128K to compress, but not in a virtually contiguous buffer, so
> you need the algorithm to support streaming of 4K chunks.  And the LZ4
> implementation doesn't properly support that.  (Note that this is a property of
> the LZ4 *implementation*, not the LZ4 *format*.)
> 
> How about using vm_map_ram() to get a contiguous buffer, like what f2fs does?
> Then you wouldn't need streaming support.
> 
> There is some overhead in setting up page mappings, but it might actually turn
> out to be faster (also for the other algorithms, not just LZ4) since it avoids
> the overhead of streaming, such as the algorithm having to copy all the data
> into an internal buffer for matchfinding.

Yes the mapping allows to compress the buffer in one go but the overhead
is not small. I had it in one of the prototypes back then too but did
not finish it because it would mean to update the on-disk compression
container format.

vm_map_ram needs to be called twice per buffer (both compression and
decompressin), there are some additional data allocated, the virual
aliases have to be flushed each time and this could be costly as I'm
told (TLB shootdowns, IPI).

Also vm_map_ram is deadlock prone because it unconditionally allocates
with GFP_KERNEL, so the scoped NOFS protection has to be in place. And
F2FS does not do that, but that's fixable.